Ho più set contenenti numeri interi. Un numero intero può essere presente in un set o in più set. Mi piacerebbe trovare / abbinare i set con gli interi più comuni.
Esempio s1 {1, 2, 3, 4} s2 {1, 3, 4, 5} s3 {6, 7, 8, 9} s4 {1, 6, 8, 10}
In questo caso, vorrei "efficientemente" raggruppare s1 + s2 poiché hanno gli elementi più sovrapposti (3) seguiti da s3 + s4 (2) s1 + s4 (1).
Puoi farlo in modo bruto (abbina tutte le possibilità - poi ordina) Alla ricerca di un modo efficace per farlo.
Ho fatto qualcosa di simile qualche anno fa. Nel mio caso avevamo decine di migliaia di set e ogni set aveva una dozzina di interi. Non tutti i set hanno lo stesso numero di numeri interi. Poiché questi sono "insiemi", suppongo che l'ordine degli interi in ciascun set sia irrilevante.
Nel nostro caso, il passaggio 1 consisteva nel calcolare un hash dei numeri di ciascun set. Dovremmo quindi ordinare l'elenco degli hash e tirare fuori i duplicati.
Il passaggio 2 consisteva nel calcolare l'hash di ogni insieme meno un elemento, quindi fare lo stesso. Ad esempio,
s1 {1,2,3,4} darebbe 4 hash (2,3,4) e (1,3,4) e (1,2,4) e (1,2,3).
Creeremo una nuova lista associando tutti i 4 hash con s1 e sort / look per i duplicati. Questo avrebbe trovato la (1,3,4) corrispondenza tra s1 e s2.
Faremmo un passo simile 3 (omettendo 2 da ciascun set) e così via. Ci sono voluti alcuni esperimenti per capire dove fosse il taglio / costo. Questo è sicuramente un costoso metodo di forza bruta, ma ha funzionato bene per noi.
Suppongo che tutti i tuoi set siano della stessa dimensione (cioè lo stesso numero di elementi)
Per gli insiemi ordinati si ordina sul primo elemento O (nlog (n)), quindi si inizia il partizionamento in classi di equivalenza.
Per una determinata dimensione dell'insieme, questo sarà O (nlog (n)) nel complesso, per n il numero di serie. Non è O (mlog (m)) per m, il numero di elementi impostati (dimensione dei set).
Questo è simile a un diagramma di Voronoi su una metrica speciale.
Ho appena notato che assumi serie non ordinate, questa risposta da teorico CS ha una buona soluzione basata sull'hash, ci possono ancora essere collisioni hash, ma puoi ridurle quanto vuoi, all'interno della macchina Precisione del computer ...
Leggi altre domande sui tag algorithms sorting