Python fusiona la lista múltiple con la intersección

Posible duplicado:
Python: fusión simple de la lista basada en intersecciones

Tengo una lista múltiple:

list=[[1,2,3],[3,5,6],[8,9,10],[11,12,13]] 

¿Existe una forma inteligente y rápida de obtener todas las listas secundarias con al menos una intersección? En mi ejemplo quiero que el código vuelva

  result=[[1,2,3,5,6],[8,9,10],[11,12,13]] 

Esto funciona, pero tal vez no sea muy elegante:

 def merge_lists(l): s=map(set, l) i, n=0, len(s) while i < n-1: for j in xrange(i+1, n): if s[i].intersection(s[j]): s[i].update(s[j]) del s[j] n-=1 break else: i+=1 return [sorted(i) for i in s] 

¡Buena pregunta! Es mucho más simple si lo considera como un problema de componentes conectados en un gráfico. El siguiente código utiliza la excelente biblioteca de gráficos networkx y la función de pairs de esta pregunta .

 def pairs(lst): i = iter(lst) first = prev = item = i.next() for item in i: yield prev, item prev = item yield item, first lists = [[1,2,3],[3,5,6],[8,9,10],[11,12,13]] import networkx g = networkx.Graph() for sub_list in lists: for edge in pairs(sub_list): g.add_edge(*edge) networkx.connected_components(g) [[1, 2, 3, 5, 6], [8, 9, 10], [11, 12, 13]] 

Explicación

Creamos un nuevo gráfico (vacío) g . Para cada sub-lista en las lists , considere sus elementos como nodos del gráfico y agregue un borde entre ellos. (Ya que solo nos importa la conexión, no necesitamos agregar todos los bordes, ¡solo los adyacentes!) Tenga en cuenta que add_edge toma dos objetos, los trata como nodos (y los agrega si aún no están allí), y Añade una ventaja entre ellos.

Luego, simplemente encontramos los componentes conectados del gráfico, ¡un problema resuelto! – y sacarlos como nuestros conjuntos de intersección.

Puede hacer esto esencialmente con un solo paso a través de los datos:

 list_of_lists = [[1, 2, 3], [3, 5, 6], [8, 9, 10], [11, 12, 13]] sets = {} for lst in list_of_lists: s = set(lst) t = set() for x in s: if x in sets: t.update(sets[x]) else: sets[x] = s for y in t: sets[y] = s s.update(t) ids = set() for s in sets.itervalues(): if id(s) not in ids: ids.add(id(s)) print s 

Esto crea un sets diccionarios sets asigna cada elemento al conjunto al que pertenece. Si algún elemento se ha visto anteriormente, su conjunto se subsume en el actual y se actualizan todas las entradas disciplinarias que se asignan al conjunto anterior.

Finalmente, necesitamos encontrar todos los conjuntos únicos en los valores de los sets diccionarios. Tenga en cuenta que mientras implementé esto como un diccionario de conjuntos, el código también funciona con listas en lugar de conjuntos.