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

Question

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

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

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

Answer 1

Вы имели в виду что-то вроде ниже? (Питон):

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

Answer 2

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

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

Итак, если Лицо А находится в группе 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 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
}

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