Algoritmo per la fusione di set che condividono almeno 2 elementi

Question

Dato un elenco di set:

• S_1: [1, 2, 3, 4]
• S_2: [3, 4, 5, 6, 7]
• S_3: [8, 9, 10, 11]
• S_4: [1, 8, 12, 13]
• S_5: [6, 7, 14, 15, 16, 17]

Qual è il modo più efficiente per unire tutti i set che condividono almeno 2 elementi? Suppongo che questo sia simile a un problema di componenti connessi. Quindi il risultato sarebbe:

• [1, 2, 3, 4, 5, 6, 7, 14, 15, 16, 17] (S_1 UNION S_2 UNION S_5)
• [8, 9, 10, 11]
• [1, 8, 12, 13] (S_4 condivide 1 con S_1 e 8 con S_3, ma non uniti perché condividono solo un elemento in ciascuno)

L'implementazione ingenua è O (N ^ 2), dove N è il numero di insiemi, il che non è fattibile per noi. Ciò dovrebbe essere efficace per milioni di set.

Answer 1

Let there be a list of many Sets named (S)

Perform a pass through all elements of S, to determine the range (LOW .. HIGH).

Create an array of pointer to Set, of dimensions (LOW, HIGH), named (M).

do
    Init all elements of M to NULL.   

    Iterate though S, processing them one Set at a time, named (Si).

        Permutate all ordered pairs in Si. (P1, P2) where P1 <= P2.
        For each pair examine M(P1, P2)
            if M(P1, P2) is NULL
                Continue with the next pair.
            otherwise
                Merge Si, into the Set pointed to by, M(P1, P2).
                Remove Si from S, as it has been merged.
                Move on to processing Set S(i + 1)

        If Si was not merged, 
            Permutate again through Si
            For each pair, make M(P1, P2) point to Si.

while At least one set was merged during the pass.

La mia testa sta dicendo che riguarda l'ordine (2N ln N). Prendilo con un granello di sale.

Answer 2

Se puoi ordinare gli elementi nel set, puoi esaminare usando Mergesort su i set. L'unica modifica necessaria è verificare la presenza di duplicati durante la fase di unione. Se ne viene trovato uno, basta scartare il duplicato. Poiché mergesort è O (n * log (n)), questo offrirà una velocità maggiore rispetto all'algoritmo O (n ^ 2) ingenuo.

Tuttavia, per essere davvero efficace, è necessario mantenere un set ordinato e mantenerlo ordinato, in modo da poter saltare la fase di ordinamento e passare direttamente alla fase di unione.

Answer 3

Non vedo come si possa fare in meno di O (n ^ 2).

Ogni set deve essere confrontato con gli altri per vedere se contengono 2 o più elementi condivisi. Sono n * (n-1) / 2 confronti, quindi O (n ^ 2), anche se il controllo degli elementi condivisi richiede tempo costante.

Nell'ordinamento, l'implementazione ingenua è O (n ^ 2) ma puoi trarre vantaggio dalla natura transitiva del confronto ordinato (quindi, ad esempio, non sai che nulla nella partizione inferiore di quicksort deve essere confrontato con qualsiasi cosa in la partizione superiore, poiché è già stata confrontata con il perno). Questo è il risultato dell'ordinamento O (n * log n).

Questo non si applica qui. Quindi, a meno che non ci sia qualcosa di speciale nei set che ci consente di saltare i confronti in base ai risultati dei confronti precedenti, sarà O (n ^ 2) in generale.

Paul.

Answer 4

Una nota a margine: dipende dalla frequenza con cui si verifica. Se la maggior parte delle coppie di insiemi condividono almeno due elementi, potrebbe essere più efficiente costruire il nuovo insieme nello stesso momento in cui si passa attraverso il confronto e gettarlo via se non lo fanno abbinare la condizione. Se la maggior parte delle coppie non condivide almeno due elementi, il rinvio della costruzione del nuovo set fino a quando la conferma della condizione potrebbe essere più efficiente.

Answer 5

Se i tuoi elementi sono di natura numerica o possono essere ordinati in modo naturale (ad es. puoi assegnare un valore come 1, 2, 42 ecc ...), suggerirei di utilizzare un ordinamento radix sui set uniti, e fai un secondo passaggio per raccogliere gli elementi unici.

Questo algoritmo dovrebbe essere di O (n) e puoi ottimizzare un po 'l'ordinamento radix usando operatori di spostamento bit a bit e maschere di bit. Ho fatto qualcosa di simile per un progetto a cui stavo lavorando e funziona come un fascino.