Algoritmo de membresía común

Question

Las personas pueden pertenecer a uno o muchos grupos. ¿Cuál es un buen algoritmo para generar membresías comunes?

es decir, las personas A y B están en los grupos C, D y E ... etc.

Mi idioma preferido sería Ruby (o quizás Python), pero cualquier código o seudocódigo sería muy apreciado.

Answer 1

Es un algoritmo muy simple, en realidad (al menos para un número razonable de usuarios y grupos).

Considere que cada usuario es un conjunto cuyos elementos son los grupos de los que son miembros. Para encontrar los grupos que dos usuarios tienen en común, simplemente tome la intersección de los conjuntos de membresía de esos dos usuarios.

Entonces, si la Persona A está en el Grupo K, M y N, y la Persona B está en K, N y P, tendría los siguientes conjuntos:

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

En Ruby, puede usar la clase de biblioteca estándar Set para realizar estos 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

¿Querías decir algo como lo de abajo? (python):

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

Answer 3

¿Estás tratando de encontrar algo en particular sobre las membresías? ¿O simplemente estás tratando de encontrar todas las membresías ... Es decir:

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

Si es lo último, no creo que haya un algoritmo especial para hacer esto; siempre y cuando verificar que una persona esté en un grupo tome O (1), su mejor opción es el algoritmo de fuerza bruta 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 está buscando la intersección de conjuntos, existen muchos otros algoritmos ... pero este problema en particular no es nada especial.