通用成员算法

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

你的意思是下面的东西吗？ （蟒蛇）：

>>> 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
}

如果您正在寻找集合的交集，那么还有许多其他算法......但这个特殊问题并不特别。