Unione di tutti gli insiemi intersecanti

Question

Dato un elenco di oggetti con più attributi di cui ho bisogno per trovare la lista dei set creati da un'unione di tutti i sottoinsiemi che si intersecano.

In particolare si tratta di oggetti persona, ognuno con molti attributi. Ho bisogno di creare un elenco di gruppi 'master' in base a una manciata di identificatori unici come SSN, DLN, ecc.

Per esempio, se la persona A e la persona B hanno lo stesso SSN che creare un set i. Poi, se la persona B e C hanno la stessa DLN, essi creare un set II. Persona D ed E hanno lo stesso SSN ma (e tutti gli altri identificatori) non corrisponde a nessuno degli identificatori delle persone A, B o C. Dopo l'unione tutti i sottoinsiemi intersecano voglio finire con un insieme con Persone A, B, C e un altro set con Persone D, e.

Ecco il pseudo-codice per la mia soluzione. Sono curioso di sapere se qualcuno ha già messo a punto un modo più efficiente di fondere tutti i possibili insiemi si intersecano. Tenete a mente che i legami tra gruppi potrebbero essere x persone lungo (vale a dire A partite B da SSN e B corrisponde C da DLN e C corrisponde D dal SSN e D corrisponde E da qualche altro identificativo si tradurrebbe in Persone A-E in un set). assumere anche che la lingua questo sarà attuato in supporti impostato operazioni.

bigSetList = array of all of the uniq Sets
fullyTested = false
while (bigSetList.size() > 1) or (fullyTested is false)
    foreach thisSet in bigSetList  order by size desc
        if count(sets that intersect with thisSet) > 0
            newThisSet = thisSet
            intersectingSets = []
            bigSetList.delete(thisSet)
            foreach testSet in bigSetList
                if thisSet.intersects(testSet)
                    newThisSet.addAll(testSet)
                    intersectingSets.push(testSetID)
                end if
            end
            bigSetList.delete(intersectingSets)
            bigSetList.push(newThisSet)
            bigSetList.sort()
            break
        end if
    end foreach
    fullyTested = true  // have looped through every set in the list and found 0 intersect partners
end

Answer 1

Per espandere il mio commento nel post originale, si vuole creare un elenco di gruppi in cui ogni membro di un determinato set di azioni almeno un attributo con almeno un altro membro di quel gruppo.

Ingenuamente, questo può essere risolto o trovando tutte le coppie che condividono un attributo e fondendo insieme coppie che hanno lo stesso partner iterativamente. Questo sarebbe O (N ^ 3) (N ^ 2 per l'iterazione di coppie, e fino a N insiemi separati per determinare l'appartenenza).

Si può anche pensare a questo problema, come la determinazione della componente connessa di un grafico , dove ogni oggetto e ogni valore di attributo univoco è un nodo; ogni oggetto sarebbe collegato a ciascuno dei suoi valori di attributo. Impostazione che grafico sarebbe voluto tempo lineare, e si potrebbe determinare i componenti collegati in tempo lineare, con una larghezza o profondità prima ricerca.

Answer 2

Direi che si dispone di un insieme relativamente piccolo di attributi per l'oggetto Person (rispetto al numero di oggetti Person si sta valutando). Se si vuole ridurre l'attraversamento lista degli oggetti Person più volte, si può prendere una persona, mettere i suoi attributi in una lista di possibili connessioni conosciute e poi passare alla persona successiva. Con ogni persona successiva, si vede se è collegato a qualsiasi connessione precedente. Se è così, quindi si aggiunge le sue caratteristiche uniche alle possibili connessioni. Si dovrebbe essere in grado di elaborare tutti gli oggetti Person in un solo passaggio. E 'possibile che avrete alcuni set sconnesse nei risultati, quindi potrebbe essere la pena di esaminare gli oggetti Person scollegati dopo aver creato il primo grafico.

Answer 3

while (!people.isEmpty()) {
    Person first = people.get(0);
    people.remove(first);
    Set<Person> set = makeSet(first);
    for (Person person : people) {
        for (Person other : set) {
            if (person.isRelatedTo(other)) {
                set.add(person);
                people.remove(person);
            }
        }
    }
    sets.add(set);
}
for (Set<Person> a : sets) {
    for (Set<Person> b : sets.except(a)) {
        for (Person person : a)
            for (Person other : b) {
                if (person.isRelatedTo(other)) {
                    a.addAll(b);
                    b.clear();
                    sets.remove(b);
                    break;
                }
            }
    }
}

Answer 4

In primo luogo, c'è qualche gerarchia inerente identificatori, e non in contraddizione con gli identificatori di un più alto sorta annullare lo stesso identificatore di una specie inferiore? Ad esempio, se A e B hanno la stessa SSN, B e C hanno la stessa DLN, e C e D hanno lo stesso SSN, che non corrisponde a una e SSN di B, vuol dire che ci sono due gruppi o uno?

Supponendo che le contraddizioni non contano, avete a che fare con classi di equivalenza, come utente 57368 (sconosciuto Google) stati. Per le classi di equivalenza, le persone si rivolgono spesso a struttura Union-trovare . Per quanto riguarda come eseguire queste unioni, non è immediatamente banale, perché presumo che non avere il collegamento diretto A-B quando entrambi A e B hanno la stessa SSN. Invece, i nostri set sarà composto da due tipi di elementi. Ogni coppia (attribute type, attribute value) = attribute è un elemento. Hai anche elementi corrispondenti a objects. Quando si scorrere l'elenco degli attributi di un oggetto, eseguire la (object, attribute) unione.

Una delle caratteristiche più importanti della struttura dei dati Unione-trovare è che la struttura risultante rappresenta l'insieme. E ti permette di interrogare "Che set è A?" Se questo non è sufficiente, fatecelo sapere e possiamo migliorare il risultato.

Ma la caratteristica più importante è che l'algoritmo ha qualcosa che assomiglia comportamento costante in tempo per ogni unione e di query operazione.

Answer 5

Così il vostro esempio di raccolta potrebbe essere la seguente:

A { ss |-> 42, dl |-> 123 }
B { ss |-> 42, dl |-> 456 }
C { ss |-> 23, dl |-> 456 }
D { ss |-> 89, dl |-> 789 }
E { ss |-> 89, dl |-> 432 }

Poi vorrei suggerire di usare un algoritmo dove si accumulano multi-collezioni in modo incrementale la fusione o l'inserimento di ogni collezione nei multi-collezioni:

L'iterazione 1. La prima collezione diventa l'unico multi-raccolta:

{A} { ss |-> [42], dl |-> [123] }

Iterazione 2. Unisci la prossima collezione nella prima dal SSN è già presente:

{A,B} { ss |-> [42], dl |-> [123,456] }

L'iterazione 3. Unire di nuovo, dal momento che il DLN è già presente:

{A,B,C} { ss |-> [23,42], dl |-> [123,456] }

Iterazione 4. Inserire un nuovo multi-raccolta poiché non v'è alcuna corrispondenza:

{A,B,C} { ss |-> [23,42], dl |-> [123,456] }
{D}     { ss |-> [89],    dl |-> [789]     }

Iterazione 5. fondersi con la seconda raccolta multimateriale, dal momento che lo SSN è lì:

{A,B,C} { ss |-> [23,42], dl |-> [123,456] }
{D,E}   { ss |-> [89],    dl |-> [432,789] }

Quindi, in ogni iterazione (uno per ogni collezione), è necessario identificare tutti multi-collezioni che hanno valori in comune con la raccolta si elaborano e si fondono tutti questi insieme.

In generale, se ci sono n collezioni ciascuna con un numero k costante di attributi, allora questo algoritmo verrà eseguito in tempo O (nnk) = O (n ² ). Il comportamento nel caso peggiore si exibited se tutti i valori degli attributi sono distinti. Quando c'è più condivisione tra i valori degli attributi, il tempo che ci vuole per inserire e determinare l'appartenenza nei set di valore di attributo (ad esempio [23,42]) viene ad essere il fattore dominante, in modo che il set di valori attributo deve essere efficiente.

Se si utilizza insiemi disgiunti ottimali , allora ogni Trova o Unisci il funzionamento verrà eseguito nel tempo ammortizzato O (α (n)).

In questo modo, per ogni iterazione ci saranno al massimo n multi-collezioni (la situazione in cui non multi-collezioni sono state unite finora). Per integrare la nuova collezione nei multi-collezioni, è necessario eseguire un'operazione di ricerca su ciascuno dei multi-collezioni k set per identificare tutti i multi-collezioni da unire, che richiede tempo delimitata da O (nkα (n)) . Per unire l'al massimo k multi-collezioni trovato in questo modo prende O (k ² α (n)).

Quindi per tutti iterazione il tempo è delimitata da O (n (nkα (n) + k ² α (n))) = O (n (nkα (n))) = O ( n ² Ka (n)) = O (n ² α (n)) poiché k è una costante.

Poiché α (n) per tutti gli scopi pratici è una costante, il tempo totale è delimitata da O (n ² ).