Algorithme d'appartenance commun

Question

Les personnes peuvent appartenir à un ou plusieurs groupes. Qu'est-ce qu'un bon algorithme pour générer des appartenances communes?

-à-dire, les personnes A et B sont dans les groupes C, D et E ... etc

Ma langue préférée serait Ruby (ou peut-être Python), mais tout code ou pseudocode seraient grandement appréciés .

Answer 1

Il est un algorithme très simple, en fait (au moins pour un nombre raisonnable d'utilisateurs et des groupes).

Considérez chaque utilisateur comme un ensemble dont les éléments sont les groupes dont ils sont membres. Pour trouver les groupes que deux utilisateurs ont en commun, il suffit de prendre l'intersection des ensembles d'appartenance de ces deux utilisateurs.

Donc, si la personne A est dans le groupe K, M et N, et personne B est en K, N et P, vous avez les jeux suivants:

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

Dans Ruby, vous pouvez utilisez la classe de bibliothèque standard Set pour effectuer ces calculs:

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

Essayez-vous de trouver quelque chose en particulier sur les adhésions? Ou êtes-vous juste essayer de trouver toutes les adhésions ... à savoir:

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

Si elle est celle-ci, je ne pense pas qu'il y ait un algorithme spécial pour le faire; Tant que vérifier qu'une personne est dans un groupe prend O (1) votre meilleur pari est l'algorithme de force brute 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 
} 

Si vous cherchez l'intersection des ensembles, il y a beaucoup d'autres algorithmes là-bas ... mais ce problème particulier n'a rien de spécial.

Answer 3

Voulez-vous dire quelque chose comme ci-dessous? (Python):

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