Algoritmo per trovare gruppi di relazioni comuni

Question

Algoritmo per trovare gruppi di relazioni comuni

Naviga le tue risposte

#1 da (1 voti)

0

Ho un set di dati molto grande con due colonne di interesse: Nome e Cugino.

Ogni riga ha un nome univoco e ogni nome ha un cugino.

I dati sono reciprocamente inclusivi, quindi il nome del cugino apparirà anche come un'altra riga nei dati.

L'effetto è quindi un grande set di dati con molti nomi di persone collegate tra loro.

Le relazioni, tuttavia, si formano in gruppi separati. Questi sono gruppi che non hanno alcuna relazione con nessuna persona in nessun altro gruppo.

E.g (usando - > per indicare una relazione)

A- > C- > E- > G = Gruppo 1
B- > D- > F- > H = Group 2

Nessuna delle persone nel Gruppo 1 condivide una relazione con una persona del Gruppo 2.

Quindi, sto cercando un approccio per trovare questi gruppi di persone correlate usando solo i loro nomi e relazioni. Questo potrebbe essere uno pseudo-codice o un approccio concettuale, qualsiasi cosa che mi indichi la strada giusta.

Set di dati di esempio:

Name Cousin  
A    C  
B    D 
C    E  
D    F  
E    G  
F    H  
G    E
H    K
I    M  
K    H  
M    I

Questi dati saranno aggregati in tre gruppi: Gruppo 1 (A, C, E, G); Gruppo 2 (B, D, F, H, K); Gruppo 3 (I, M).

algorithms

posta Chris M 05.06.2015 - 16:10

fonte

1 risposta

Leggi altre domande sui tag algorithms

Esiste un modo per eseguire operazioni bit a bit con più di due stati Api per CMS e applicazioni mobili separate o uguali

score 1 · Accepted Answer

Stai costruendo una serie di grafici.

Inizia e inizi a camminare nell'elenco delle relazioni che hai ottenuto.

A -> C

Quindi, facciamo un grafico che lo rappresenta.

A - C

E poi hai:

B -> D

Né B né D sono rappresentati in nessuno dei grafici al momento. Quindi ora hai:

A - C       

B - D

E poi C - > E, quindi cerchiamo C e colleghiamo a E. Ora abbiamo:

A - C - E   

B - D

E così via. Ciò ti darà la possibilità di darti tutti i relativi grafici.

"Bene", si dice, "ma questo non si avvicina molto a un'implementazione"

Il problema reale qui è come rappresentare i grafici.

Consente di scrivere alcuni pseudocodici. Parlo un dialetto perlish - ma non è perl.

$nextGroup = 1
for each ($key, $link) in (@row) {
    if(not defined $group{$key}) {
        $group{$key} = $nextGroup++;
    }
    if(not defined $group{$link} || $group{$link} == $group{$key}) {
        $group{$link} = $group{$key}
    } else {
        for each ($k, $v) in (entries %group) {
            if($v == $group{$link}) {
                $group{$k} = $group{$key};
            }
        }
    }
}

Che cosa sta facendo? Itera su ogni riga restituita. Se la chiave non è un elemento conosciuto, la assegna a un nuovo gruppo. Assegna quindi al gruppo la chiave che appartiene al collegamento. Se il link ha già un valore diverso , trova tutti i link con lo stesso valore e li assegna al valore della chiave.

Quindi, iniziamo di nuovo.

A = 1 (nextGroup = 2)
  C = 1
B = 2 (nextGroup = 3)
  D = 2
C is 1
  E = 1
D = 3 (nextGroup = 4)
  F = 3
E is 1
  G = 1
...

Alla fine di questo, la mappa dei gruppi / dizionario / hash (qualunque sia la tua lingua lo chiami) avrà ogni individuo lì dentro con un valore corrispondente. Tutte le voci con lo stesso valore appartengono allo stesso grafico raffigurato.