共通メンバーシップアルゴリズム

Question

人は1つまたは複数のグループに属することができます。一般的なメンバーシップを出力するための良いアルゴリズムは何ですか？

ie、個人AおよびBはグループC、D、およびEに属します...など

優先する言語はRuby（または多分 Python）ですが、コードまたは擬似コードは大歓迎です。

Answer 1

これは非常に単純なアルゴリズムで、実際には（少なくとも妥当な数のユーザーとグループに対して）。

各ユーザーがメンバーであるグループを要素とするセットであると考えてください。 2人のユーザーが共通に持っているグループを見つけるには、それら2人のユーザーのメンバーシップセットの共通部分を取得します。

したがって、個人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
}

セットの共通部分を探している場合、他にも多くのアルゴリズムがあります...しかし、この特定の問題は特別なものではありません。