Algoritmo de assinatura comum
-
22-07-2019 - |
Pergunta
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.
Solução
É 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
Outras dicas
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'])
>>>
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.