Questo problema è noto, AFAIK, come "partizionamento di un set in classi di equivalenza", ma non sono riuscito a trovare ad hoc una buona risorsa web per questo, quindi provo a dare un profilo generale di un algoritmo efficiente:
La parte esterna è semplice:
Inizia con un set vuoto di benne. Ogni bucket contiene un elenco di persone e, per ogni coppia di bucket diversi, gli indirizzi email comuni delle persone associate di ciascun bucket saranno disgiunti in qualsiasi momento.
-
itera su tutte le persone P
-
Per ogni indirizzo email di P: determina se esiste già un bucket correlato - > ti fornisce una lista B di bucket (che potrebbero essere vuoti)
-
se B è vuoto (nessuno degli indirizzi email di P corrisponde a nessuno dei bucket precedenti), crea un nuovo bucket che contiene solo questa persona
-
se B contiene esattamente un elemento, metti P in quel bucket (ed estendi di conseguenza l'elenco di indirizzi email del bucket)
-
se B contiene 2 o più bucket, unisci questi bucket in uno (ed estendi di conseguenza l'elenco di indirizzi email di questo nuovo bucket)
Quindi non resta che scegliere alcune efficienti strutture dati che supportano le operazioni richieste:
-
ogni bucket deve contenere un gruppo di persone - > un elenco di persone per ciascun bucket lo farà
-
efficiente aggiunta di persone a un bucket e fusione di bucket - > un elenco è ancora valido
-
efficiente ricerca di bucket via email: significa che hai bisogno di un dizionario aggiuntivo D che mappa email -> bucket .
Quest'ultimo può essere aggiornato in modo efficiente quando viene aggiunto un nuovo bucket, quando un bucket riceve altri indirizzi e-mail o quando verranno uniti due bucket (il che significa che gli indirizzi e-mail nel dizionario dovranno essere rimappati nella fusione appena creata benna).
Per recuperare definitivamente tutti i bucket trovati, puoi fare un po 'di contabilità durante il processo sui bucket appena creati e quelli che sono stati cancellati durante l'unione (alcuni hashset aggiuntivi per tutti i bucket validi faranno il trucco), o tu può scorrere tutti i valori di quel dizionario e rimuovere i bucket duplicati (vedere alcune soluzioni Java standard qui ).
Lo schizzo sopra può essere reso ancora più efficiente utilizzando la cosiddetta "struttura dei dati disgiunti" invece di un elenco di persone per ciascun bucket, ma per la mia esperienza per molte applicazioni pratiche è sufficiente un elenco.
