Algoritmo de assinatura comum

Question

As pessoas podem pertencer a um ou vários grupos. O que é um bom algoritmo para membros comuns de saída?

isto é, pessoas que A e B são em grupos C, D, e E, etc ...

O meu idioma preferido seria Ruby (ou talvez Python), mas qualquer código ou pseudocódigo seria muito apreciada.

Answer 1

É um algoritmo muito simples, na verdade (pelo menos para os números razoáveis ??de usuários e grupos).

Considere cada usuário a ser um conjunto cujos elementos são os grupos dos quais eles são um membro. Para encontrar os dois grupos de usuários têm em comum, simplesmente tomar a intersecção de conjuntos de adesão desses dois usuários.

Assim, se a pessoa A está no Grupo K, M e N, e Pessoa B está em K, N e P, você teria os seguintes conjuntos:

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

Em Ruby, você pode usar o Set classe biblioteca padrão para realizar estes cálculos:

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

Você quis algo média como a seguir? (Python):

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

Answer 3

Você está tentando encontrar qualquer coisa em particular sobre as associações? Ou você está apenas tentando encontrar todas as associações ... Ou seja:

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

Se ele é o último, eu não acho que há um algoritmo especial para fazer isso; enquanto verificar se uma pessoa está em um grupo leva O (1) a sua melhor aposta é a O (M * N) algoritmo de força bruta.

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
}

Se você está procurando a intersecção de conjuntos, há muitos outros algoritmos lá fora ... mas este problema em particular é nada de especial.