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

Question

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

то есть лица A и B находятся в группах C, D и E ... и т. д.

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

Answer 1

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

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

Таким образом, если лицо A находится в группах K, M и 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

Вы имели в виду что-то подобное ниже? (Python):

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

Answer 3

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

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
}

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