partición de una lista de conjuntos de elementos compartidos

Question

Aquí está la jist del problema: Dada una lista de conjuntos, tales como:

[ (1,2,3), (5,2,6), (7,8,9), (6,12,13), (21,8,34), (19,20) ] 

devolver una lista de grupos de los conjuntos, tales que los conjuntos que han compartido elemento están en el mismo grupo.

[ [ (1,2,3), (5,2,6), (6,12,13) ], [ (7,8,9), (21,8,34) ], [ (19,20) ] ] 

Nota del stickeyness - el conjunto (6,12,13) ​​no tiene un elemento compartido con (1,2,3), pero llegar a poner en el mismo grupo a causa de (5,2 , 6).

Para complicar las cosas, debo mencionar que en realidad no tienen estos conjuntos ordenados, sino más bien una tabla de base de datos con varios millones de filas que se parece a:

element | set_id 
---------------- 
1  | 1 
2  | 1 
3  | 1 
5  | 2 
2  | 2 
6  | 2 

y así sucesivamente. Así que me encantaría una forma de hacerlo en SQL, pero estaría contento con una dirección general para la solución.

EDIT: Cambié los nombres de las columnas de la tabla a (elemento, set_id) en lugar de (tecla, ID_grupo), para hacer los términos más consistentes. Tenga en cuenta que la respuesta de Kev usa los nombres de las columnas antiguas.

Answer 1

El problema es exactamente el cálculo de los componentes conectados de un hipergraph: los enteros son los vértices, y los conjuntos son los hyperedges. Una forma habitual de calcular los componentes conectados es inundando ellos uno tras otro:

• para todo i = 1 a N, hacer:
• si i ha sido etiquetado por algunos j < i, a continuación, continuar (me refiero a saltar a la siguiente i)
• flood_from otra cosa (i, i)

donde flood_from (i, j) se define como

• para cada conjunto S que contiene i, si ya no está etiquetado por j entonces:
• etiqueta S por j y para cada elemento k de S, si k aún no está etiquetado por j, entonces márquelo por j, y invoca flood_from (k, j)

Las etiquetas de los juegos le proporcionan los componentes conectados que está buscando.

---

En términos de bases de datos, el algoritmo puede expresarse de la siguiente manera: se agrega una columna de etiqueta a su base de datos y calcular el componente conectado del conjunto i haciendo

• S = Seleccionar todo filas donde set_id == i
• conjunto de etiquetas para i para las filas en S
• S '= seleccionar todas las filas donde TAG no está establecido y donde elemento es en el elemento (S)
• mientras que S' no está vacía , haz
• ---- conjunto de etiquetas para i para las filas en S '
• ---- S ''= seleccionar todas las filas donde no se establece TAG y donde elemento es en el elemento (S')
• -
• set_id retorno --- S = S unión S '
• ---- S' = S '' (S)

---

Otra manera (teórica) de la presentación de este algoritmo sería para decir que estás buscando los puntos fijos de un mapeo:

• si A = {A , ..., A _n} es un conjunto de conjuntos, definir la unión (A) = A unión ...Unión A _n
• si K = {k , ..., K _p} es un conjunto de números enteros, defina incidencias (K) = el conjunto de conjuntos que se cruzan K

Entonces, si S es un conjunto, el componente conectado de S se obtiene mediante la iteración (incidencias) O (unión) en S hasta que se alcanza un punto fijo:

1. K = S
2. K'= incidencias (unión (K)).
3. si K == K 'y luego volver K, de lo contrario K = K' e ir a 2.

Answer 2

Podría pensar que es un problema de gráfico donde el conjunto (1,2,3) está conectado al conjunto (5,2,6) a través de la 2. Y luego utilizar un algoritmo estándar para refinar el sub conectado -graphs.

Aquí hay una aplicación Python rápida:

nodes = [ [1,2,3], [2,4,5], [6,7,8], [10,11,12], [7,10,13], [12], [] ] 
links = [ set() for x in nodes ] 

#first find the links 
for n in range(len(nodes)): 
    for item in nodes[n]: 
     for m in range(n+1, len(nodes)): 
      if (item in nodes[m]): 
       links[n].add(m) 
       links[m].add(n) 

sets = [] 
nodes_not_in_a_set = range(len(nodes)) 

while len(nodes_not_in_a_set) > 0: 
    nodes_to_explore = [nodes_not_in_a_set.pop()] 
    current_set = set() 
    while len(nodes_to_explore) > 0: 
     current_node = nodes_to_explore.pop() 
     current_set.add(current_node) 
     if current_node in nodes_not_in_a_set: 
      nodes_not_in_a_set.remove(current_node) 
     for l in links[current_node]: 
      if l not in current_set and l not in nodes_to_explore: 
       nodes_to_explore.append(l) 
    if len(current_set) > 0: 
     sets.append(current_set) 

for s in sets: 
    print [nodes[n] for n in s] 

de salida:

[[]] 
[[6, 7, 8], [10, 11, 12], [7, 10, 13], [12]] 
[[1, 2, 3], [2, 4, 5]] 

Answer 3

Esto es probablemente bastante ineficiente, pero debería funcionar, al menos: Comience con una clave, seleccionar todos los grupos que contienen esa tecla, seleccione todas las teclas de esos grupos, seleccione todos los grupos que contienen esas teclas, etc., y tan pronto como un paso no agregue nuevas claves o grupos, usted tiene una lista de todos los grupos de un sub-gráfico. Excluya esos y repita desde el principio hasta que no le queden datos.

En términos de SQL esto necesitaría un procedimiento almacenado, creo. WITH RECURSIVE puede ayudarte de alguna manera, pero todavía no tengo ninguna experiencia con él, y no estoy seguro de que esté disponible en tu back-end de DB.

Answer 4

Después de pensar en esta un poco más, se me ocurrió esto:

1. Crear una tabla llamada groups con columnas (group_id, set_id)
2. Ordenar la tabla sets por element. Ahora debería ser fácil encontrar elementos duplicados.
3. Iterar a través de la mesa de juegos, y cuando encuentre un elemento duplicado hacer:
   1. si uno de los campos set_id existe en la tabla groups, agregue el otro con la misma group_id.
   2. Si ninguno de los set_id existe en la tabla groups, genere una nueva ID de grupo y agregue ambos set_id a la tabla groups.

Al final debe tener una tabla groups que contiene todos los conjuntos.

Esto no es SQL puro, pero parece como O (nlogn), así que supongo que puedo vivir con eso.

Matt's answer Parece más correcto, pero no estoy seguro de cómo implementarlo en mi caso.