共同的成员国算法

Question

人们可以属于一个或多个组。什么是一个很好的算法，输出共成员？

即，人A和B是在组C，d和E ...等

我的偏好的语言将是红宝石（或也许的Python），但任何代码或伪代码，将不胜感激。

Answer 1

这是一个非常简单的算法，实际上是（至少对于用户和组的合理的数字）。

考虑每个用户是一组，其元素为基团，其中它们的部件。为了找到组两个用户具有共同的，简单地把这些两个用户隶属集的交集。

因此，如果人A是在组K，M，和N，和Person 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_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
}

如果你正在寻找的集合的交集，也有很多其他的算法有...但这个特殊的问题是没有什么特别的。