python - example - Reemplace la lista de la lista con la lista "condensada" de la lista mientras mantiene el orden

product() python (7)

Tengo una lista de la lista como en el código que adjunto. Quiero vincular cada sub lista si hay valores comunes. Entonces quiero reemplazar la lista de la lista con una lista condensada de la lista. Ejemplos: si tengo una lista [[1,2,3],[3,4]] quiero [1,2,3,4] . Si tengo [[4,3],[1,2,3]] quiero [4,3,1,2] . Si tengo [[1,2,3],[a,b],[3,4],[b,c]] quiero [[1,2,3,4],[a,b,c]] o [[a,b,c],[1,2,3,4]] No me importa cuál.

Ya casi estoy allí...

Mi problema es cuando tengo un caso como [[1,2,3],[10,5],[3,8,5]] Quiero [1,2,3,10,5,8] pero con mi código actual que obtengo [1,2,3,8,10,5]

Aquí está mi código:

import itertools a = [1,2,3] b = [3,4] i = [21,22] c = [88,7,8] e = [5,4] d = [3, 50] f = [8,9] g= [9,10] h = [20,21] lst = [a,b,c,i,e,d,f,g,h,a,c,i]*1000 #I have a lot of list but not very many different lists def any_overlap(a, b): sb = set(b) return any(itertools.imap(sb.__contains__, a)) def find_uniq(lst): '''''' return the uniq parts of lst'''''' seen = set() seen_add = seen.add return [ x for x in lst if x not in seen and not seen_add(x)] def overlap_inlist(o_lst, lstoflst): '''''' Search for overlap, using "any_overlap", of a list( o_lst) in a list of lists (lstoflst). If there is overlap add the uniq part of the found list to the search list, and keep track of where that list was found '''''' used_lst =[ ] n_lst =[ ] for lst_num, each_lst in enumerate(lstoflst): if any_overlap(o_lst,each_lst): n_lst.extend(each_lst) used_lst.append(lst_num) n_lst= find_uniq(n_lst) return n_lst, used_lst def comb_list(lst): '''''' For each list in a list of list find all the overlaps using ''ovelap_inlist''. Update the list each time to delete the found lists. Return the final combined list. '''''' for updated_lst in lst: n_lst, used_lst = overlap_inlist(updated_lst,lst) lst[:] = [x for i,x in enumerate(lst) if i not in used_lst] lst.insert(0,n_lst) return lst comb_lst = comb_list(lst) print comb_lst

La salida de este script es:

[[88, 7, 8, 9, 10], [1, 2, 3, 4, 50, 5], [21, 22, 20]]

Lo quiero así que las llaves están en el orden original como:

[[88, 7, 8, 9, 10], [1, 2, 3, 4, 5, 50,], [21, 22, 20]]

El 5 y el 50 se cambian en nuevo lst [2]

Soy algo nuevo en python. Agradecería cualquier solución al problema o comentarios sobre mi código actual. No soy un experto en informática, me imagino que puede haber algún tipo de algoritmo que haga esto rápidamente (¿tal vez de la teoría de conjuntos?). Si existe un algoritmo de este tipo, indíqueme la dirección correcta.

Puede que sea más complicado de lo que es ... ¡Gracias!

Aquí está mi enfoque. Utiliza el concepto de un "conjunto disjunto" para identificar primero qué sublistas se superponen entre sí, luego las une, eliminando los duplicados.

from collections import OrderedDict def disjoint_set_find(djs, node): # disjoint set find, with path compression if node not in djs: # base case, node is a root of a set return node djs[node] = disjoint_set_find(djs, djs[node]) # recurse, caching results return djs[node] def disjoint_set_union(djs, first, second): first = disjoint_set_find(djs, first) # find root of first set second = disjoint_set_find(djs, second) # and of second set if first < second: # make smaller root the root of the new combined set djs[second] = first elif second < first: djs[first] = second # deliberately ignore the case where first == second (same set) def condenseBK(*master_list): values = OrderedDict() # maps values to the first sublist containing them overlaps = {} # maps sublist indexes to each other to form a disjoint set for i, sublist in enumerate(master_list): for v in sublist: if v not in values: # no overlap, so just store value values[v] = i else: # overlap detected, do a disjoint set union disjoint_set_union(overlaps, values[v], i) output = [] # results output_map = {} # map from original indexes to output indexes for v, i, in values.items(): # iterate over values in order root = disjoint_set_find(overlaps, i) if root not in output_map: output_map[i] = len(output) output.append([]) # create new output sublists as necessary output[output_map[root]].append(v) return output

Salida de muestra:

>>> a = [1,2,3] >>> b = [3,4] >>> c = [88,7,8] >>> d = [3, 50] >>> e = [5,4] >>> f = [8,9] >>> g = [9,10] >>> h = [20,21] >>> i = [21,22] >>> lst = [a,b,c,i,e,d,f,g,h,a,c,i]*1000 >>> condenseBK(*lst) [[1, 2, 3, 4, 5, 50], [88, 7, 8, 9, 10], [21, 22, 20]]

Una explicación del algoritmo:

Por solicitud, aquí hay una explicación de cómo funciona mi código.

Las dos primeras funciones implementan las operaciones de find y union de un conjunto desunido . La estructura de datos se implementa con un diccionario que asigna nodos a sus nodos principales. Cualquier nodo que no sea una clave del diccionario es la root de un conjunto. La operación de find devuelve el nodo raíz del conjunto que contiene un node determinado. Para ayudar un poco al rendimiento, he implementado la "compresión de ruta", que reduce el número de pasos recursivos necesarios con el tiempo. La operación de union combina los conjuntos que contienen sus argumentos first y second .

La función de condense principal tiene dos partes. Primero, configura un par de estructuras de datos, luego las usa para construir la salida.

values es un OrderedDictionary que se asigna de cada valor al índice de la primera lista secundaria en la que se encuentra. El orden en que se agrega cada valor se utiliza para producir la salida en el orden correcto.

overlaps es el diccionario utilizado como para el conjunto disjoint. Sus nodos son los índices enteros de sublistas superpuestas.

Los primeros bucles llenan esas dos estructuras de datos. Recorren los sublistas y sus contenidos. Si un valor no se ha visto anteriormente, se agrega al diccionario de values . Si se ha visto, la sublista actual está superponiendo una sublista anterior que contiene ese valor.

Para resolver la superposición, el código hace una unión de los conjuntos disjuntos que contienen las dos sublistas.

La salida está incorporada en la lista de output . Debido a que es probable que haya menos sublistas de salida de las que había en la entrada, necesitamos un diccionario adicional para asignar entre los índices antiguos (de la entrada) a los nuevos índices que se aplican a la lista de salida.

Para completar la lista de resultados, iteramos sobre los valores, lo que sucede en el orden en que se agregaron gracias al uso de la clase OrderedDict. Usando el conjunto disjoint, puede combinar las listas superpuestas correctamente.

Este algoritmo tiene un rendimiento muy bueno cuando hay muchas listas para procesar que no se superponen inmediatamente. Por ejemplo, este conjunto de 200 listas de tres elementos en última instancia, todas se superponen, pero solo comienza a ver las superposiciones después de que se hayan procesado las primeras 100:

lst2 = [list(range(4*i, 4*(i+1)-1)) for i in range(100)] + / [list(range(4*i+2, 4*(i+1)+1)) for i in range(100)]

Aquí hay un enfoque de fuerza bruta (podría ser más fácil de entender):

from itertools import chain def condense(*lists): # remember original positions positions = {} for pos, item in enumerate(chain(*lists)): if item not in positions: positions[item] = pos # condense disregarding order sets = condense_sets(map(set, lists)) # restore order result = [sorted(s, key=positions.get) for s in sets] return result if len(result) != 1 else result[0] def condense_sets(sets): result = [] for candidate in sets: for current in result: if candidate & current: # found overlap current |= candidate # combine (merge sets) # new items from candidate may create an overlap # between current set and the remaining result sets result = condense_sets(result) # merge such sets break else: # no common elements found (or result is empty) result.append(candidate) return result

Ejemplo

>>> condense([1,2,3], [10,5], [3,8,5]) [1, 2, 3, 10, 5, 8] >>> a = [1,2,3] >>> b = [3,4] >>> i = [21,22] >>> c = [88,7,8] >>> e = [5,4] >>> d = [3, 50] >>> f = [8,9] >>> g= [9,10] >>> h = [20,21] >>> condense(*[a,b,c,i,e,d,f,g,h,a,c,i]*1000) [[1, 2, 3, 4, 5, 50], [88, 7, 8, 9, 10], [21, 22, 20]] >>> condense([1], [2, 3, 2]) [[1], [2, 3]]

Comparación de rendimiento

condense_*() funciones de condense_*() provienen de las respuestas a esta pregunta. lst_OP lista de entrada de la pregunta (tamaño diferente), lst_BK - la lista de prueba de la respuesta de @ Blckknght (tamaño diferente). Vea la fuente .

Las mediciones muestran que las soluciones basadas en conceptos de "conjuntos disjuntos" y "componentes conectados de gráficos no dirigidos" se comportan de manera similar en ambos tipos de entrada.

name time ratio comment condense_hynekcer 5.79 msec 1.00 lst_OP condense_hynekcer2 7.4 msec 1.28 lst_OP condense_pillmuncher2 11.5 msec 1.99 lst_OP condense_blckknght 16.8 msec 2.91 lst_OP condense_jfs 26 msec 4.49 lst_OP condense_BK 30.5 msec 5.28 lst_OP condense_blckknght2 30.9 msec 5.34 lst_OP condense_blckknght3 32.5 msec 5.62 lst_OP name time ratio comment condense_blckknght 964 usec 1.00 lst_BK condense_blckknght2 1.41 msec 1.47 lst_BK condense_blckknght3 1.46 msec 1.51 lst_BK condense_hynekcer2 1.95 msec 2.03 lst_BK condense_pillmuncher2 2.1 msec 2.18 lst_BK condense_hynekcer 2.12 msec 2.20 lst_BK condense_BK 3.39 msec 3.52 lst_BK condense_jfs 544 msec 563.66 lst_BK name time ratio comment condense_hynekcer 6.86 msec 1.00 lst_rnd condense_jfs 16.8 msec 2.44 lst_rnd condense_blckknght 28.6 msec 4.16 lst_rnd condense_blckknght2 56.1 msec 8.18 lst_rnd condense_blckknght3 56.3 msec 8.21 lst_rnd condense_BK 70.2 msec 10.23 lst_rnd condense_pillmuncher2 324 msec 47.22 lst_rnd condense_hynekcer2 334 msec 48.61 lst_rnd

Para reproducir los resultados, clone gist y ejecute measure-performance-condense-lists.py

Esta solución utiliza solo un diccionario ordenado.
deepcopy () es necesario si uno quiere que la copia original permanezca sin cambios.

from collections import OrderedDict from copy import deepcopy def treat(passed_list): L = deepcopy(passed_list) dic = OrderedDict() for subl in L: for x in subl: if x not in dic: dic[x] = subl print ''dic at start'' print ''/n''.join(''%-3s : %s'' % (a,dic[a]) for a in dic) + ''/n'' for sublist in L: short = [] short.extend(el for el in sublist if el not in short) seen = [] for k,val in dic.iteritems(): if val is sublist: break if k in short: if val not in seen: seen.append(val) sumseen = [] for elseen in seen: for y in elseen: sumseen.append(y) dic[y] = sumseen if seen: for el in sublist: if el not in sumseen: sumseen.append(el) dic[el] = sumseen sublist[:] = short cumul = [] cumul.extend(lu for lu in dic.itervalues() if lu not in cumul) return cumul plus = [[1,2,3,2,1],[10,5,5,5,10], [8,5,3,3,5],[45,50,12,45,40,12]] lst = [[1,2,3], [10,5], [3,8,5]] for one_list in (plus,lst): print ''one_list before == %r/n'' % one_list print ''treat(one_list) == %r/n'' % treat(one_list) print ''one_list after == %r/n'' % one_list print ''====================================''

resultado

one_list before == [[1, 2, 3, 2, 1], [10, 5, 5, 5, 10], [8, 5, 3, 3, 5], [45, 50, 12, 45, 40, 12]] dic at start 1 : [1, 2, 3, 2, 1] 2 : [1, 2, 3, 2, 1] 3 : [1, 2, 3, 2, 1] 10 : [10, 5, 5, 5, 10] 5 : [10, 5, 5, 5, 10] 8 : [8, 5, 3, 3, 5] 45 : [45, 50, 12, 45, 40, 12] 50 : [45, 50, 12, 45, 40, 12] 12 : [45, 50, 12, 45, 40, 12] 40 : [45, 50, 12, 45, 40, 12] treat(one_list) == [[1, 2, 3, 10, 5, 8], [45, 50, 12, 40]] one_list after == [[1, 2, 3, 2, 1], [10, 5, 5, 5, 10], [8, 5, 3, 3, 5], [45, 50, 12, 45, 40, 12]] ==================================== one_list before == [[1, 2, 3], [10, 5], [3, 8, 5]] dic at start 1 : [1, 2, 3] 2 : [1, 2, 3] 3 : [1, 2, 3] 10 : [10, 5] 5 : [10, 5] 8 : [3, 8, 5] treat(one_list) == [[1, 2, 3, 10, 5, 8]] one_list after == [[1, 2, 3], [10, 5], [3, 8, 5]] ====================================

Esta solución tiene un inconveniente: es 2 a 3 veces más lenta que la solución de JF Sebastian.

Estoy seguro de que hay una forma más limpia de hacerlo, pero empecé por un cierto camino e hice lo que tenía que hacer para que funcionara sin ninguna refactorización.

lookup = {} out = [] index = 0 for grp in lst: keys = [lookup.get(num, None) for num in grp] keys = [key for key in keys if key is not None] if len(keys): if len(set(keys)) != 1: for num in grp: out[keys[0]].append(num) seen = set() keys = [key for key in keys if key not in seen and not seen.add(key)] for key in keys[1:]: out[keys[0]].extend(out[key]) del out[key] seen = set() out[keys[0]] = [item for item in out[keys[0]] if item not in seen and not seen.add(item)] else: for num in grp: lookup[num] = keys[0] out[keys[0]].extend(grp) seen = set() out[keys[0]] = [item for item in out[keys[0]] if item not in seen and not seen.add(item)] else: out.append(grp) for num in grp: lookup[num] = index index += 1 print out

Gracias a @Steven por la técnica de reducción de lista con el set.

SALIDA

[[1, 2, 3, 4, 5, 50], [88, 7, 8, 9, 10], [21, 22, 20]]

Intenté escribir una solución rápida y legible . Nunca sé que es mucho más lento que otras soluciones, pero a veces puede ser mucho más rápido porque además está optimizado para sublistas más largas o para muchos sublistas que son subconjuntos de cualquier grupo existente. (Esto está motivado por el texto de la pregunta "Tengo mucha lista pero no muchas listas diferentes"). El código utiliza menos memoria solo para datos condensados que pueden ser mucho menos que los datos originales. Puede funcionar, por ejemplo, con un generador que recopila datos de un proceso en tiempo real. La estimación de complejidad es O (n log n). Creo que ningún algoritmo que usa ordenación puede ser de complejidad lineal.

def condense(lists): groups = {} # items divided into groups {id(the_set): the_set,...} members = {} # mapping from item to group positions = {} # mapping from item to sequential ordering iposition = 0 # counter for positions for sublist in lists: if not sublist or members.get(sublist[0], set()).issuperset(sublist): continue # speed-up condition if all is from one group common = set([x for x in sublist if x in members]) if common: # any common group can be a destination for merge dst_group = members[common.pop()] common = common - dst_group # are more groups common for sublist? while common: grp = members[common.pop()] if len(grp) > len(dst_group): # merge shorter into longer grp grp, dst_group = dst_group, grp dst_group.update(grp) for item in grp: members[item] = dst_group del groups[id(grp)] common = common - dst_group else: # or create a new group if nothing common dst_group = set() groups[id(dst_group)] = dst_group newitems = [] for item in sublist: # merge also new items if item not in positions: positions[item] = iposition iposition += 1 newitems.append(item) members[item] = dst_group dst_group.update(newitems) return [sorted(x, key=positions.get) for x in groups.values()]

Es más rápido que pillmuncher2 para subslists más largas que aproximadamente 8 elementos porque puede trabajar en más elementos juntos. También es muy rápido para listas con muchas sublistas similares o muchas sublistas que son subconjuntos de cualquier grupo existente. Es más rápido en un 25% sobre pillmuncher2 para lst_OP, pero más lento en un 15% para lst_BK.

Un ejemplo de datos de prueba con sublistas largos es [list(range(30)) + [-i] for i in range(100)] .

Intencionalmente escribí "common = common - dst_group" en lugar de usar el operador set -= o "set.difference_update", porque la actualización en el lugar no es efectiva si el conjunto del lado derecho es mucho más grande que el lado izquierdo.

Solución modificada de la pastilla para facilitar la lectura. La modificación es un poco más lenta que la original debido a la sustitución de un generador por list.append. Probablemente la solución rápida más legible.

# Modified pillmuncher''s solution from collections import defaultdict def condense(lists): neighbors = defaultdict(set) # mapping from items to sublists positions = {} # mapping from items to sequential ordering position = 0 for each in lists: for item in each: neighbors[item].update(each) if item not in positions: positions[item] = position position += 1 seen = set() see = seen.add for node in neighbors: if node not in seen: unseen = set([node]) # this is a "todo" set next_unseen = unseen.pop # method alias, not called now group = [] # collects the output while unseen: node = next_unseen() see(node) unseen |= neighbors[node] - seen group.append(node) yield sorted(group, key=positions.get)

Su problema es esencialmente una gráfica teórica, el problema de los componentes conectados, con un requisito adicional con respecto al orden de los elementos de cada componente.

En su programa, el conjunto de todas las listas forma un gráfico no dirigido, donde cada lista es un nodo en el gráfico. Decimos que dos listas están conectadas directamente si tienen elementos comunes y conectadas indirectamente, si existe una tercera lista a la que ambas están conectadas, directa o indirectamente. Dados, por ejemplo, tres listas [a, b], [b, c] y [c, d], entonces [a, b] y [b, c] están conectados directamente, así como [b, c] y [c, d], pero [a, b] y [c, d] están conectados indirectamente, ya que si bien no comparten elementos comunes, ambos comparten elementos con la misma lista [b, c].

Un grupo de nodos es un componente conectado si todos los nodos del grupo están conectados (directa o indirectamente) y ningún otro nodo en el gráfico está conectado a ningún nodo del grupo.

Existe un algoritmo de tiempo lineal bastante simple que genera todos los componentes conectados en un gráfico no dirigido. Usando eso, podemos definir una función que genere todas las listas de listas disjuntas condensadas, mientras mantenemos el orden de sus elementos:

from itertools import imap, combinations_with_replacement from collections import defaultdict def connected_components(edges): neighbors = defaultdict(set) for a, b in edges: neighbors[a].add(b) neighbors[b].add(a) seen = set() def component(node, neighbors=neighbors, seen=seen, see=seen.add): unseen = set([node]) next_unseen = unseen.pop while unseen: node = next_unseen() see(node) unseen |= neighbors[node] - seen yield node for node in neighbors: if node not in seen: yield component(node) def condense(lists): tuples = combinations_with_replacement(enumerate(imap(tuple, lists)), 2) overlapping = ((a, b) for a, b in tuples if not set(a[1]).isdisjoint(b[1])) seen = set() see = seen.add for component in connected_components(overlapping): yield [item for each in sorted(component) for item in each[1] if not (item in seen or see(item))] print list(condense([[1, 2, 3], [10, 5], [3, 8, 5], [9]])) print list(condense([[1, 2, 3], [5, 6], [3, 4], [6, 7]]))

Resultado:

[[1, 2, 3, 10, 5, 8], [9]] [[5, 6, 7], [1, 2, 3, 4]]

La complejidad de tiempo de condense() es cuadrática, ya que cada lista debe compararse con todas las demás para descubrir si tienen elementos comunes. Por lo tanto, el rendimiento es horrible. ¿Podemos mejorarlo de alguna manera? Sí.

Dos listas se conectan directamente si tienen elementos comunes. Podemos cambiar esta relación: dos elementos se conectan directamente si pertenecen a la misma lista, y se conectan indirectamente si existe un tercer elemento que está conectado (directa o indirectamente) a ambos. Dados, por ejemplo, dos listas [a, b] y [b, c], entonces a y b están conectados directamente, así como b y c, y por lo tanto a y c están conectados indirectamente. Si también adaptamos la idea de JFSebastians de almacenar la posición de la primera aparición de cada elemento, podemos implementarlo de la siguiente manera:

def condense(lists): neighbors = defaultdict(set) positions = {} position = 0 for each in lists: for item in each: neighbors[item].update(each) if item not in positions: positions[item] = position position += 1 seen = set() def component(node, neighbors=neighbors, seen=seen, see=seen.add): unseen = set([node]) next_unseen = unseen.pop while unseen: node = next_unseen() see(node) unseen |= neighbors[node] - seen yield node for node in neighbors: if node not in seen: yield sorted(component(node), key=positions.get)

Todavía utiliza el algoritmo de componentes conectados, pero esta vez vemos los elementos como conectados, no como listas. Los resultados son los mismos que antes, pero como la complejidad del tiempo ahora es lineal, se ejecuta mucho más rápido.

class List(list): pass rv = dict() def condense_step(): """find and merge one overlapping pair in rv""" for i, iv in rv.items(): for j, jv in rv.items(): if i != j and i.intersection(j): m = i.union(j) del rv[i] del rv[j] rv.setdefault(m, []) rv[m] += iv rv[m] += jv return True def unique(l): """flatten list-of-lists excluding duplicates""" seen = set() for i in sum(l, []): if i not in seen: seen.add(i) yield i def condense(inp): rv.clear() inp = map(List, inp) for i in range(len(inp)): inp[i].order = i rv.setdefault(frozenset(inp[i]), []) rv[frozenset(inp[i])].append(inp[i]) while condense_step(): pass for v in rv.values(): v.sort(key=lambda x: x.order) return [list(unique(i)) for i in rv.values()]