공통 멤버십 알고리즘

Question

사람들은 하나 또는 많은 그룹에 속할 수 있습니다. 공통 멤버십을 출력하기위한 좋은 알고리즘은 무엇입니까?

즉, 사람 A와 B는 그룹 C, D 및 E ... 등에 있습니다.

내가 선호하는 언어는 루비 (또는 아마도 Python), 그러나 모든 코드 또는 의사 코드는 크게 높이 평가 될 것입니다.

Answer 1

실제로는 매우 간단한 알고리즘입니다. 실제로 (적어도 합리적인 수의 사용자와 그룹의 경우).

각 사용자가 요소가 구성원 인 그룹 인 세트로 간주하십시오. 두 사용자가 공통점을 가진 그룹을 찾으려면 두 사용자의 멤버십 세트의 교차로를 사용하십시오.

따라서 사람 A가 그룹 K, M 및 N이고 개인 B가 K, N 및 P에 있으면 다음 세트가 있습니다.

A := {K, M, N}
B := {K, N, P}
intersect(A, B) = {K, N}

루비에서는 표준 라이브러리 클래스를 사용할 수 있습니다. 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) Brute Force 알고리즘입니다.

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
}

세트의 교차점을 찾고 있다면 다른 많은 알고리즘이 있습니다. 그러나이 특정 문제는 특별한 것이 아닙니다.