Palloni e Cesti Ver2

Question

Oltre alle palle e cestini originali problema che ho citato qui: Palloni e Cesti Problema Algoritmo

C'è un problema leggermente diverso.

Ancora ci sono N persone e hanno le palle illimitate, ma essi non hanno cesti questa volta.

Il problema è:

Ci sono N persone con palline illimitate e M diversi cestini. La gente lanciare palle ai cestini.

voglio trovare gruppi di persone che stanno gettando le palle agli stessi cestini.

Una persona getta a Cesti 1, 2, 4,, 6,7, 14, 51, 32 La persona B getta a Cesti 3, 4, 6, 7, 14,15, 16, 64,43 Persona C getta a Cesti 3, 4, 6,7,5, 87, 42, 32, 52, 55 . . . ecc.

In questo esempio, la persona A e B possono essere ben collegati (diciamo amici) (4,6,7,14 comune) e C può essere collegato anche a loro ma non così ben collegato. (4, 6,7 comune)

Voglio trovare gruppi di 4-5 persone del genere in un database molto grande di persone.

Answer 1

L'idea di Jackson è l'inizio.

Dopo aver trovato le cricche, definire il paniere comune set per ogni cricca, dall'intersezione di cesti tutte le egdes'. (Dove cesti di un bordo sono i cestini comuni alle persone rappresentate da nodi di questo bordo). solo se il cesto comune definito è maggiore di X, allora questa cricca rappresenta un gruppo davvero collegata.

Ad esempio, nella domanda iniziale, i bordi sarebbero:

A-B:  weight=4, baskets=[4,6,7,14]
A-C:  weight=3, baskets=[4,6,7]
B-C:  weight=4, baskets=[3,4,6,7]

se potare a meno di 3, si ottiene che si tratta di una cricca, con cesto comune set = [4,6,7].

nel esempio che ha dato nel commento alla risposta di Jackson, il set cestello comune sarebbe vuoto, in modo da sapere che questi ragazzi non sono realmente collegati.

Answer 2

Ok, la mia idea iniziale; modellare questo come un grafo pesato. Rendere le persone i vertici e creare un collegamento quando condividono un cestino. Se condividono più canestri quindi aumentare il peso del collegamento per ogni canestro che condividono. Quindi nel tuo esempio, il peso del bordo tra A e B sarebbe 4.

È quindi possibile decidere come accogliente tutti in un gruppo deve essere, potare i bordi che hanno un peso inferiore a tale valore e poi cercare cricche del grafico risultante.