Algoritmo di appartenenza comune

Question

Le persone possono appartenere a uno o più gruppi. Qual è un buon algoritmo per generare appartenenze comuni?

ovvero, le persone A e B fanno parte dei gruppi C, D, E ... ecc.

La mia lingua preferita sarebbe Ruby (o forse Python), ma qualsiasi codice o pseudocodice sarebbe molto apprezzato.

Answer 1

In realtà è un algoritmo molto semplice (almeno per un numero ragionevole di utenti e gruppi).

Considera ogni utente come un insieme i cui elementi sono i gruppi di cui sono membri. Per trovare i gruppi che due utenti hanno in comune, basta prendere l'intersezione dei set di appartenenza di quei due utenti.

Quindi, se la persona A è nel gruppo K, M e N e la persona B è in K, N e P, avresti i seguenti set:

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

In Ruby, puoi utilizzare la classe di libreria standard Set per eseguire questi calcoli:

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

Intendi qualcosa di simile al seguente? (Python):

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

Answer 3

Stai cercando di trovare qualcosa in particolare sulle iscrizioni? O stai solo cercando di trovare tutte le iscrizioni ... Ie:

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

Se è quest'ultimo, non penso che ci sia un algoritmo speciale per farlo; fintanto che verificare che una persona sia in un gruppo prende O (1) la tua scommessa migliore è l'algoritmo O (M * N) della forza 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 stai cercando l'intersezione di insiemi, ci sono molti altri algoritmi là fuori ... ma questo particolare problema non è niente di speciale.