Python: aplanar listas anidadas con índices

Dada una lista de listas anidadas arbitralmente profundas de tamaño arbitrario, me gustaría un iterador plano y de profundidad sobre todos los elementos del árbol, pero con indicaciones de ruta de manera que:

for x, y in flatten(L), x == L[y[0]][y[1]]...[y[-1]]. 

Es decir

 L = [[[1, 2, 3], [4, 5]], [6], [7,[8,9]], 10] flatten(L) 

debe rendir:

 (1, (0, 0, 0)), (2, (0, 0, 1)), (3, (0, 0, 2)), (4, (0, 1, 0)), (5, (0, 1, 1)), (6, (1, 0)), (7, (2, 0)), (8, (2, 1, 0)), (9, (2, 1, 1)), (10, (3,)) 

Hice una implementación recursiva para esto usando generadores con declaraciones de yield :

 def flatten(l): for i, e in enumerate(l): try: for x, y in flatten(e): yield x, (i,) + y except: yield e, (i,) 

pero no creo que sea una implementación buena o responsable. ¿Hay alguna receta para hacer esto de manera más general, simplemente usando builtins o cosas itertools como itertools ?

Creo que tu propia solución está bien, que no hay nada realmente más simple, y que la biblioteca estándar de Python no ayudaría. Pero aquí hay otra manera, que funciona de forma iterativa en lugar de recursiva, por lo que puede manejar listas muy anidadas.

 def flatten(l): stack = [enumerate(l)] path = [None] while stack: for path[-1], x in stack[-1]: if isinstance(x, list): stack.append(enumerate(x)) path.append(None) else: yield x, tuple(path) break else: stack.pop() path.pop() 

Mantengo las listas actualmente “activas” en una stack de iteradores de enumerate , y la ruta del índice actual como otra stack. Luego, en un bucle while, siempre trato de tomar el siguiente elemento de la lista actual y manejarlo adecuadamente:

  • Si el siguiente elemento es una lista, presiono su iterador de enumerate en la stack y hago espacio para el índice más profundo en la stack de la ruta del índice.
  • Si el siguiente elemento es un número, lo cedo junto con su ruta.
  • Si no había ningún elemento siguiente en la lista actual, entonces lo elimino (o más bien su iterador) y su punto de índice de las stacks.

Manifestación:

 >>> L = [[[1, 2, 3], [4, 5]], [6], [7,[8,9]], 10] >>> for entry in flatten(L): print(entry) (1, (0, 0, 0)) (2, (0, 0, 1)) (3, (0, 0, 2)) (4, (0, 1, 0)) (5, (0, 1, 1)) (6, (1, 0)) (7, (2, 0)) (8, (2, 1, 0)) (9, (2, 1, 1)) (10, (3,)) 

Tenga en cuenta que si procesa las entradas sobre la marcha, como lo hace la impresión, entonces simplemente podría mostrar la ruta como la lista que es, es decir, usar el yield x, path . Manifestación:

 >>> for entry in flatten(L): print(entry) (1, [0, 0, 0]) (2, [0, 0, 1]) (3, [0, 0, 2]) (4, [0, 1, 0]) (5, [0, 1, 1]) (6, [1, 0]) (7, [2, 0]) (8, [2, 1, 0]) (9, [2, 1, 1]) (10, [3]) 

De esta manera, el iterador solo toma O (n) tiempo para toda la iteración, donde n es el número total de objetos en la estructura (tanto listas como números). Por supuesto, la impresión aumenta la complejidad, al igual que la creación de las tuplas. Pero eso queda fuera del generador y la “falla” de la impresión o lo que sea que esté haciendo con cada ruta. Si, por ejemplo, solo observa la longitud de cada ruta en lugar de su contenido, lo que toma O (1), entonces todo es incluso O (n).

Dicho todo esto, una vez más, creo que tu propia solución está bien. Y claramente más simple que esto. Y como comenté en la respuesta de @naomik, creo que su solución no poder manejar listas de profundidad de alrededor de 1000 o más es bastante irrelevante. En primer lugar, ni siquiera se debería tener tal lista. Si uno lo hace, es un error que debería ser arreglado en su lugar. Si la lista también puede ampliar , como en su caso, y está equilibrada, incluso con un factor de ramificación de solo 2 se quedaría sin memoria a una profundidad muy por debajo de 100 y no llegaría a cerca de 1000. Si la lista no puede extenderse, entonces las listas anidadas son la elección incorrecta de la estructura de datos, además, en primer lugar, no estaría interesado en la ruta del índice. Si puede ampliarse pero no lo hace , entonces diría que el algoritmo de creación debería mejorarse (por ejemplo, si representa un árbol ordenado, agregue el equilibrio).

Acerca de mi solución otra vez: además de su capacidad para manejar listas profundas arbitrarias y su eficiencia, encuentro interesantes algunos de sus detalles:

  • Rara vez se ven objetos enumerate que se almacenan en algún lugar. Por lo general, solo se usan en loops & Co directamente, como for i, x in enumerate(l):
  • Teniendo la path[-1] lista para aparecer y escribiendo en ella con la for path[-1], x in ...
  • El uso de un for loop con una break inmediata y una twig else , para iterar sobre el siguiente valor único y manejar los extremos con gracia sin try / except y sin el next y algunos valores predeterminados.
  • Si yield x, path , es decir, no convierta cada ruta en una tupla, entonces realmente necesita procesarla directamente durante la iteración. Por ejemplo, si hace una list(flatten(L)) , obtiene [(1, []), (2, []), (3, []), (4, []), (5, []), (6, []), (7, []), (8, []), (9, []), (10, [])] . Es decir, “todas” las rutas de índice estarán vacías. Por supuesto, eso es porque realmente solo hay un objeto de ruta que actualizo y cedo una y otra vez, y al final está vacío. Esto es muy similar a itertools.groupby , donde por ejemplo [list(g) for _, g in list(groupby('aaabbbb'))] le da [[], ['b']] . Y no es una mala cosa. Recientemente escribí sobre eso extensamente .

Versión más corta con una stack que contiene ambos índices y enumerate objetos alternativamente:

 def flatten(l): stack = [None, enumerate(l)] while stack: for stack[-2], x in stack[-1]: if isinstance(x, list): stack += None, enumerate(x) else: yield x, stack[::2] break else: del stack[-2:] 

A partir de la recursión directa y las variables de estado con valores predeterminados

 def flatten (l, i = 0, path = (), acc = []): if not l: return acc else: first, *rest = l if isinstance (first, list): return flatten (first, 0, path + (i,), acc) + flatten (rest, i + 1, path, []) else: return flatten (rest, i + 1, path, acc + [ (first, path + (i,)) ]) print (flatten (L)) # [ (1, (0, 0, 0)) # , (2, (0, 0, 1)) # , (3, (0, 0, 2)) # , (4, (0, 1, 0)) # , (5, (0, 1, 1)) # , (6, (1, 0)) # , (7, (2, 0)) # , (8, (2, 1, 0)) # , (9, (2, 1, 1)) # , (10, (3,)) # ] 

El progtwig anterior comparte la misma debilidad que el tuyo; No es seguro para listas profundas. Podemos usar el estilo de paso de continuación para hacerlo recursivo, cambios en negrita

 def identity (x): return x # tail-recursive, but still not stack-safe, yet def flatten (l, i = 0, path = (), acc = [] , cont = identity ): if not l: return cont ( acc ) else: first, *rest = l if isinstance (first, list): return flatten (first, 0, path + (i,), acc , lambda left: flatten (rest, i + 1, path, [] , lambda right: cont ( left + right ) )) else: return flatten (rest, i + 1, path, acc + [ (first, path + (i,)) ] , cont ) print (flatten (L)) # [ (1, (0, 0, 0)) # , (2, (0, 0, 1)) # , (3, (0, 0, 2)) # , (4, (0, 1, 0)) # , (5, (0, 1, 1)) # , (6, (1, 0)) # , (7, (2, 0)) # , (8, (2, 1, 0)) # , (9, (2, 1, 1)) # , (10, (3,)) # ] 

Finalmente, reemplazamos las llamadas recursivas con nuestro propio mecanismo de call . Esto efectivamente secuencia las llamadas recursivas y ahora funciona para datos de cualquier tamaño y cualquier nivel de anidación. Esta técnica se llama trampolín – cambios en negrita

 def identity (x): return x def flatten (l): def loop (l, i = 0, path = (), acc = [], cont = identity): if not l: return cont (acc) else: first, *rest = l if isinstance (first, list): return call (loop , first, 0, path + (i,), acc, lambda left: call (loop , rest, i + 1, path, [], lambda right: cont (left + right))) else: return call (loop , rest, i + 1, path, acc + [ (first, path + (i,)) ], cont) return loop (l) .run () class call: def __init__ (self, f, *xs): self.f = f self.xs = xs def run (self): acc = self while (isinstance (acc, call)): acc = acc.f (*acc.xs) return acc print (flatten (L)) # [ (1, (0, 0, 0)) # , (2, (0, 0, 1)) # , (3, (0, 0, 2)) # , (4, (0, 1, 0)) # , (5, (0, 1, 1)) # , (6, (1, 0)) # , (7, (2, 0)) # , (8, (2, 1, 0)) # , (9, (2, 1, 1)) # , (10, (3,)) # ] 

¿Por qué es mejor? Hablando objetivamente, es un progtwig más completo. El hecho de que parezca más complejo no significa que sea menos eficiente.

El código proporcionado en la pregunta falla cuando la lista de entrada está anidada a más de 996 niveles de profundidad (en Python 3.x)

 depth = 1000 L = [1] while (depth > 0): L = [L] depth = depth - 1 for x in flatten (L): print (x) # Bug in the question's code: # the first value in the tuple is not completely flattened # ([[[[[1]]]]], (0, 0, 0, ... )) 

Peor aún, cuando la depth aumenta a alrededor de 2000, el código provisto en la pregunta genera un error de tiempo de ejecución GeneratorExitException .

Al usar mi progtwig, funciona para entradas de cualquier tamaño, anidadas a cualquier profundidad y siempre produce la salida correcta.

 depth = 50000 L = [1] while (depth > 0): L = [L] depth = depth - 1 print (flatten (L)) # (1, (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 49990 more...)) print (flatten (range (50000))) # [ (0, (0,)) # , (1, (1,)) # , (2, (2,)) # , ... # , (49999, (49999,)) # ] 

¿Quién tendría una lista tan profunda de todos modos? Uno de estos casos comunes es la lista enlazada que crea estructuras profundas en forma de árbol.

 my_list = [ 1, [ 2, [ 3, [ 4, None ] ] ] ] 

Dicha estructura es común porque el par más externo nos permite acceder fácilmente a las dos partes semánticas que nos interesan: el primer elemento y el rest de los elementos. La lista enlazada podría implementarse usando tuple o dict también.

 my_list = ( 1, ( 2, ( 3, ( 4, None ) ) ) ) my_list = { "first": 1 , "rest": { "first": 2 , "rest": { "first": 3 , "rest": { "first": 4 , "rest": None } } } } 

Arriba, podemos ver que una estructura sensible crea potencialmente una profundidad significativa. En Python, [] , () y {} te permiten anidar infinitamente. ¿Por qué nuestro flatten genérico debería restringir esa libertad?

En mi opinión, si va a diseñar una función genérica como flatten , deberíamos elegir la implementación que funcione en la mayoría de los casos y que tenga menos sorpresas. Una que falla repentinamente solo porque se usa una cierta estructura (profunda) es mala. El flatten utilizado en mi respuesta no es el más rápido [1] , pero no sorprende al progtwigdor con respuestas extrañas o fallos del progtwig.

[1] No mido el rendimiento hasta que importa, por lo que no he hecho nada para sintonizar más arriba. Otra ventaja discreta de mi progtwig es que puede ajustarlo porque lo escribimos. Por otra parte, si for , enumerate y yield problemas causados ​​en su progtwig, ¿qué haría para “solucionarlo”? ¿Cómo lo haríamos más rápido? ¿Cómo lo haríamos funcionar para insumos de mayor tamaño o profundidad? ¿De qué sirve un Ferrari después de que envuelve un árbol?

La recursión es un buen enfoque para aplanar listas profundamente anidadas. Su implementación también está bien hecha. Sugeriría modificarlo con esta receta similar de la siguiente manera:

Código

 from collections import Iterable def indexed_flatten(items): """Yield items from any nested iterable.""" for i, item in enumerate(items): if isinstance(item, Iterable) and not isinstance(item, (str, bytes)): for item_, idx in indexed_flatten(item): yield item_, (i,) + idx else: yield item, (i,) lst = [[[1, 2, 3], [4, 5]], [6], [7, [8, 9]], 10] list(indexed_flatten(lst)) 

Salida

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

Esto funciona de manera robusta con muchos tipos de elementos, por ejemplo, [[[1, 2, 3], {4, 5}], [6], (7, [8, "9"]), 10] .