Algoritmo para la fusión de 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]

Lo que más e forma fidedigna de fusionar todos los conjuntos que comparten al menos 2 elementos? Supongo que esto es similar a un problema de componentes conectados. Así, 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] (acciones S_4 1 con S_1, y 8 con S_3, pero no fusionadas, ya que sólo comparten un elemento en cada uno)

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

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. 

Mi opinión es cuestión de orden (2N en N). Toma eso con un grano de sal.

Answer 2

Si puede pedir los elementos en el conjunto, puede buscar usando 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 clasificación e ir directamente a la fase de fusión.

Answer 3

Una nota lateral: Depende de la frecuencia con que esto ocurra. Si la mayoría de los pares de conjuntos hacen comparten al menos dos elementos, podría ser más eficiente construir el nuevo conjunto al mismo tiempo que está recorriendo 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, difiriendo la construcción del nuevo conjunto hasta que la confirmación de la condición sea más eficiente.

Answer 4

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 utilizar una ordenación de radix en los conjuntos combinados. y haga un segundo pase para retomar los elementos únicos.

Este algoritmo debe ser de O (n), y puede optimizar bastante la ordenación de radix utilizando operadores de desplazamiento 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 5

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

Cada conjunto debe compararse con cualquier otro 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 se 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.

Paul.