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?

C'est-à-dire que les personnes A et B font partie des groupes C, D et E ... etc.

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

Answer 1

C’est un algorithme très simple, en réalité (du moins pour un nombre raisonnable d’utilisateurs et de groupes).

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

Ainsi, si la personne A appartient aux groupes K, M et N et si la personne B est aux pays K, N et P, vous obtenez les ensembles suivants:

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

En Ruby, vous pouvez utiliser la classe de bibliothèque standard Set pour effectuer les calculs suivants:

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

Vouliez-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'])
>>>

Answer 3

Est-ce que vous essayez de trouver quelque chose en particulier sur les adhésions? Ou essayez-vous simplement de trouver toutes les adhésions ... C’est-à-dire:

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

Si c’est le dernier cas, je ne pense pas qu’il existe un algorithme spécial pour le faire; tant que la vérification de la présence d’une personne dans un groupe prend O (1), votre meilleur choix 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 recherchez l'intersection d'ensembles, il existe de nombreux autres algorithmes ... mais ce problème particulier n'a rien de spécial.