arrays - programacion - Algoritmo rentable para agrupar conjuntos de conjuntos

teoria de conjuntos python

Question

¿Alguien puede ayudarme con algún algoritmo eficaz para llevar a cabo la siguiente tarea?

Obtuve un archivo de números de fila únicos con una matriz de números enteros por fila.

Necesito comprobar cada fila para ver los valores de una matriz que aparece en diferentes filas y ponerlas en un grupo. Aquí hay un ejemplo de cómo puede verse:

Numero de fila; Matriz de datos [...]

L1; [1,2,3,4,5]
L2; [2,3]
L3: [8,9]
L4: [6]
L5; [7]
L6; [5,6]

Con base en estos datos de entrada, espero que el algoritmo produzca el resultado:

Grupo N; Matriz de filas [...]

G1; [L1,L2,L4,L6]
G2; [ L3]
G3; [ L5]

PS: el conjunto de datos original representa cientos de millones de filas y puede contener casi un millón de elementos de matriz ... la eficiencia del tiempo es una preocupación.

Gracias

Answer 1

Creo que esto es equivalente a encontrar componentes conectados de un gráfico en el que:

1. Los vértices corresponden a los números iniciales de las filas
2. Hay un borde entre dos vértices x y y si hay un elemento común en la matriz para x y la matriz para y

Esto se puede hacer de manera eficiente utilizando una estructura de datos set disjuntos de la siguiente manera:

1. MakeSet(d) para cada uno de los valores de datos d (1,2,3,4,5,6,7,8,9 en su ejemplo)
2. Para cada fila con la matriz A, llame a join(A[0],A[i]) para cada opción de i.

Esto producirá un conjunto para cada componente conectado. Luego puede producir su matriz de salida iterando sobre las filas por segunda vez:

set output to an array of empty lists
for each row r
    A = array for row r
    id = find(A[0])
    output[id].append(r)

Ejemplo de código Python

from collections import defaultdict
data=[[1,2,3,4,5],
      [2,3],
      [8,9],
      [6],
      [7],
      [5,6]]
N=max(max(A) for A in data)
rank=[0]*(N+1)
parent=range(N+1)

def Find(x):
    """Find representative of connected component"""
    if  parent[x] != x:
        parent[x] = Find(parent[x])
    return parent[x]

def Union(x,y):
    """Merge sets containing elements x and y"""
    x = Find(x)
    y = Find(y)
    if x == y:
        return
    if rank[x]<rank[y]:
        parent[x] = y
    elif rank[x]>rank[y]:
        parent[y] = x
    else:
        parent[y] = x
        rank[x] += 1

# First join all data
for row,A in enumerate(data):
    for x in A:
        Union(A[0],x)

# Then place rows into sets
D=defaultdict(list)
for row,A in enumerate(data):
    D[Find(A[0])].append(row+1)

# Then display output
for i,L in enumerate(D.values()):
    print i+1,L

Al ejecutar este código, se imprime el resultado:

1 [3]
2 [1, 2, 4, 6]
3 [5]