Gemeinsame Mitgliedschaft Algorithm

Question

Die Menschen können zu einer oder mehreren Gruppen angehören. Was ist ein guter Algorithmus zur Ausgabe von gemeinsamen Mitgliedschaften?

dh Personen A und B sind in den Gruppen C, D und E ... etc

Meine bevorzugte Sprache sei Rubin (oder vielleicht Python), aber jeder Code oder Pseudo-Code würde sehr geschätzt werden.

Answer 1

Es ist ein sehr einfacher Algorithmus, eigentlich (zumindest für eine vernünftige Anzahl von Benutzern und Gruppen).

jeden Benutzer Betrachten wir einen Satz, dessen Elemente die Gruppen, von denen sie ein Mitglied sein. Um die Gruppen zwei Benutzer gemeinsam haben, nehmen Sie einfach den Schnittpunkt dieser beiden Benutzer Mitgliedschaft Sets zu finden.

Also, wenn Person A in der Gruppe K, M und N, und Person B in K, N und P, würden Sie die folgenden Sätze haben:

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

In Ruby können Sie die Standard-Bibliothek Klasse Set verwenden, um diese Berechnungen durchzuführen:

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

Haben Sie so etwas wie die unten bedeuten? (Python):

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

Answer 3

Sind Sie versuchen, etwas Bestimmtes über die Mitgliedschaften zu finden? Oder versuchen Sie einfach alle Mitgliedschaften zu finden ... Dh:

A - No group
B - Groups 1, 2, 3
C - Groups 2, 5
D - Groups 2, 3, 4

Wenn es Letzteres ist, ich glaube nicht, dass es ein spezieller Algorithmus, dies zu tun; solange die Überprüfung, dass eine Person in einer Gruppe ist, nimmt O (1) Ihre beste Wette ist, die O (M * N) Brute-Force-Algorithmus.

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
}

Wenn Sie sich für die Kreuzung von Sätzen suchen, gibt es viele andere Algorithmen gibt ... aber dieses Problem ist nichts Besonderes.