algorithm - geeksforgeeks - graph theory explained book

Algoritmo para fusionar conjuntos que comparten al menos 2 elementos

Question

Dada una lista de conjuntos:

• 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]

¿Cuál es la forma más eficiente de fusionar todos los conjuntos que comparten al menos 2 elementos? Supongo que esto es similar a un problema de componentes conectados. Entonces el resultado sería:

• [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 comparte 1 con S_1 y 8 con S_3, pero no se fusionan porque solo comparten un elemento en cada uno)

La implementación ingenua es O (N ^ 2), donde N es el número de conjuntos, lo cual no es viable para nosotros. Esto necesitaría ser eficiente para millones de conjuntos.

Answer 1

No veo cómo se puede hacer esto en menos de O (n ^ 2).

Cada conjunto debe compararse con todos los demás para ver si contienen 2 o más elementos compartidos. Eso es n * (n-1) / 2 comparaciones, por lo tanto O (n ^ 2), incluso si la verificación de los elementos compartidos lleva un tiempo constante.

En la ordenación, la implementación ingenua es O (n ^ 2) pero puede aprovechar la naturaleza transitiva de la comparación ordenada (por lo que, por ejemplo, no se debe comparar nada en la partición inferior de quicksort con nada en la partición superior , como ya se ha comparado con el pivote). Esto es lo que hace que la clasificación sea O (n * log n).

Esto no aplica aquí. Entonces, a menos que haya algo especial acerca de los conjuntos que nos permita omitir las comparaciones basadas en los resultados de comparaciones anteriores, será O (n ^ 2) en general.

Pablo.

Answer 2

Si puede ordenar los elementos en el conjunto, puede buscar usar Mergesort en los conjuntos. La única modificación necesaria es verificar si hay duplicados durante la fase de fusión. Si se encuentra uno, simplemente deseche el duplicado. Como mergesort es O (n * log (n)), esto ofrecerá velocidad implícita en comparación con el algoritmo ingenuo O (n ^ 2).

Sin embargo, para ser realmente efectivo, debe mantener un conjunto ordenado y mantenerlo ordenado, de modo que pueda omitir la fase de ordenamiento y pasar directamente a la fase de fusión.

Answer 3

Si sus elementos son de naturaleza numérica, o pueden ordenarse de forma natural (es decir, puede asignar un valor como 1, 2, 42, etc.), sugeriría usar una ordenación de radix en los conjuntos combinados, y hacer un segundo pasar para recoger los elementos únicos.

Este algoritmo debe ser de O (n), y puede optimizar bastante la clasificación de radix utilizando operadores de turno bit a bit y máscaras de bits. He hecho algo similar para un proyecto en el que estaba trabajando, y funciona como un encanto.

Answer 4

Una nota al margen: depende de la frecuencia con que esto ocurra. Si la mayoría de los pares de juegos comparten al menos dos elementos, podría ser más eficiente construir el nuevo conjunto al mismo tiempo que se avanza en la comparación, y descartarlo si no coinciden con la condición. Si la mayoría de los pares no comparten al menos dos elementos, diferir la construcción del nuevo conjunto hasta que la confirmación de la condición sea más eficiente.

Answer 5

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.

Mi cabeza dice que esto es sobre el orden (2N en N). Toma eso con un grano de sal.