Алгоритм общего членства

Question

Люди могут принадлежать одной или нескольким группам. Что такое хороший алгоритм для вывода общих членств?

т.е. лицо А и В в группах C, D и Е ... и т.д.

Моего предпочитаемый язык будет Ruby (или может быть Python), но любой код или псевдокод был бы весьма признателен ,

Answer 1

Это очень простой алгоритм, фактически (по крайней мере, для разумного количества пользователей и групп).

Рассмотрите каждого пользователя как набор, элементами которого являются группы, членом которых они являются. Чтобы найти группы, у которых есть два пользователя, просто возьмите пересечение наборов пользователей этих двух пользователей.

Таким образом, если лицо А в группе К, М и N, и лица B находится в K, N и P, вы бы следующие наборы:

A := {K, M, N} 
B := {K, N, P} 
intersect(A, B) = {K, N} 

В Ruby, вы можете используйте стандартный библиотечный класс Set для выполнения этих расчетов:

require 'set' 
memberships_a = Set[:K, :M, :N] 
memberships_b = Set[:K, :N, :P] 
shared = memberships_a.intersection(memberships_b) 
# you can also use the '&' operator as shorthand for 'intersection' 
shared_2 = memberships_a & memberships_b 

Answer 2

Вы пытаетесь найти что-либо в частности о членствах? Или вы просто пытаетесь найти все членством ... Т.е.:

A - No group 
B - Groups 1, 2, 3 
C - Groups 2, 5 
D - Groups 2, 3, 4 

Если это последнее, я не думаю, что есть специальный алгоритм, чтобы сделать это; до тех пор, пока проверка того, что человек находится в группе, принимает O (1), ваш лучший выбор - это алгоритм грубой силы O (M * N).

For each person O(N) { 
    Create a set for this person 
    For each group O(M) { 
     if the person is in the group, add this group to the set O(1) when using maps/hashed structures 
    } 
    output the set 
} 

Если вы ищете для пересечения множеств, есть много других алгоритмов, там ... но эта конкретная проблема нет ничего особенного.

Answer 3

Вы имели в виду что-то вроде нижеследующего? (python):

>>> a_groups = set(["A", "B", "C"]) 
>>> b_groups = set(["B", "C", "D"]) 
>>> print a_groups & b_groups 
set(['C', 'B']) 
>>>