Aplanar una lista irregular de listas

Sí, ya sé que este tema se ha tratado anteriormente ( aquí , aquí , aquí , aquí ), pero hasta donde sé, todas las soluciones, excepto una, fallan en una lista como esta:

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

Donde la salida deseada es

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

O quizás incluso mejor, un iterador. La única solución que vi que funciona para un anidamiento arbitrario se encuentra en esta pregunta :

 def flatten(x): result = [] for el in x: if hasattr(el, "__iter__") and not isinstance(el, basestring): result.extend(flatten(el)) else: result.append(el) return result flatten(L) 

¿Es este el mejor modelo? ¿Pasé por alto algo? ¿Algún problema?

Usar las funciones del generador puede hacer que su ejemplo sea un poco más fácil de leer y probablemente aumente el rendimiento.

Python 2

 def flatten(l): for el in l: if isinstance(el, collections.Iterable) and not isinstance(el, basestring): for sub in flatten(el): yield sub else: yield el 

Utilicé el Iterable ABC agregado en 2.6.

Python 3

En Python 3, la basestring ya no existe, pero puedes usar una tupla de str y bytes para obtener el mismo efecto allí.

El yield from operador devuelve un artículo de un generador de uno en uno. Esta syntax para delegar a un subgenerador se agregó en 3.3

 def flatten(l): for el in l: if isinstance(el, collections.Iterable) and not isinstance(el, (str, bytes)): yield from flatten(el) else: yield el 

Mi solución:

 def flatten(x): if isinstance(x, collections.Iterable): return [a for i in x for a in flatten(i)] else: return [x] 

Un poco más conciso, pero más o menos lo mismo.

Versión del generador de la solución no recursiva de @ unutbu, tal como lo solicitó @Andrew en un comentario:

 def genflat(l, ltypes=collections.Sequence): l = list(l) i = 0 while i < len(l): while isinstance(l[i], ltypes): if not l[i]: l.pop(i) i -= 1 break else: l[i:i + 1] = l[i] yield l[i] i += 1 

Versión ligeramente simplificada de este generador:

 def genflat(l, ltypes=collections.Sequence): l = list(l) while l: while l and isinstance(l[0], ltypes): l[0:1] = l[0] if l: yield l.pop(0) 

Generador mediante recursión y escritura de pato (actualizado para Python 3):

 def flatten(L): for item in L: try: yield from flatten(item) except TypeError: yield item list(flatten([[[1, 2, 3], [4, 5]], 6])) >>>[1, 2, 3, 4, 5, 6] 

Esta versión de flatten evita el límite de recursión de Python (y, por lo tanto, funciona con iterables arbitrariamente profundos y nesteds). Es un generador que puede manejar cadenas e iterables arbitrarios (incluso los infinitos).

 import itertools as IT import collections def flatten(iterable, ltypes=collections.Iterable): remainder = iter(iterable) while True: first = next(remainder) if isinstance(first, ltypes) and not isinstance(first, basestring): remainder = IT.chain(first, remainder) else: yield first 

Aquí hay algunos ejemplos que demuestran su uso:

 print(list(IT.islice(flatten(IT.repeat(1)),10))) # [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] print(list(IT.islice(flatten(IT.chain(IT.repeat(2,3), {10,20,30}, 'foo bar'.split(), IT.repeat(1),)),10))) # [2, 2, 2, 10, 20, 30, 'foo', 'bar', 1, 1] print(list(flatten([[1,2,[3,4]]]))) # [1, 2, 3, 4] seq = ([[chr(i),chr(i-32)] for i in xrange(ord('a'), ord('z')+1)] + range(0,9)) print(list(flatten(seq))) # ['a', 'A', 'b', 'B', 'c', 'C', 'd', 'D', 'e', 'E', 'f', 'F', 'g', 'G', 'h', 'H', # 'i', 'I', 'j', 'J', 'k', 'K', 'l', 'L', 'm', 'M', 'n', 'N', 'o', 'O', 'p', 'P', # 'q', 'Q', 'r', 'R', 's', 'S', 't', 'T', 'u', 'U', 'v', 'V', 'w', 'W', 'x', 'X', # 'y', 'Y', 'z', 'Z', 0, 1, 2, 3, 4, 5, 6, 7, 8] 

Aunque el flatten puede manejar generadores infinitos, no puede manejar el anidamiento infinito:

 def infinitely_nested(): while True: yield IT.chain(infinitely_nested(), IT.repeat(1)) print(list(IT.islice(flatten(infinitely_nested()), 10))) # hangs 

Aquí está mi versión funcional de aplanamiento recursivo que maneja tanto las tuplas como las listas, y le permite agregar cualquier combinación de argumentos posicionales. Devuelve un generador que produce la secuencia completa en orden, arg por arg:

 flatten = lambda *n: (e for a in n for e in (flatten(*a) if isinstance(a, (tuple, list)) else (a,))) 

Uso:

 l1 = ['a', ['b', ('c', 'd')]] l2 = [0, 1, (2, 3), [[4, 5, (6, 7, (8,), [9]), 10]], (11,)] print list(flatten(l1, -2, -1, l2)) ['a', 'b', 'c', 'd', -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] 

Aquí hay otra respuesta que es aún más interesante …

 import re def Flatten(TheList): a = str(TheList) b,crap = re.subn(r'[\[,\]]', ' ', a) c = b.split() d = [int(x) for x in c] return(d) 

Básicamente, convierte la lista anidada en una cadena, usa una expresión regular para eliminar la syntax anidada, y luego convierte el resultado de nuevo a una lista (aplanada).

 def flatten(xs): res = [] def loop(ys): for i in ys: if isinstance(i, list): loop(i) else: res.append(i) loop(xs) return res 

Podría usar deepflatten del paquete de terceros deepflatten :

 >>> from iteration_utilities import deepflatten >>> L = [[[1, 2, 3], [4, 5]], 6] >>> list(deepflatten(L)) [1, 2, 3, 4, 5, 6] >>> list(deepflatten(L, types=list)) # only flatten "inner" lists [1, 2, 3, 4, 5, 6] 

Es un iterador, por lo que debe iterarlo (por ejemplo, ajustándolo con la list o usándolo en un bucle). Internamente, utiliza un enfoque iterativo en lugar de un enfoque recursivo y está escrito como una extensión C para que pueda ser más rápido que los enfoques de python puro:

 >>> %timeit list(deepflatten(L)) 12.6 µs ± 298 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) >>> %timeit list(deepflatten(L, types=list)) 8.7 µs ± 139 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) >>> %timeit list(flatten(L)) # Cristian - Python 3.x approach from https://stackoverflow.com/a/2158532/5393381 86.4 µs ± 4.42 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) >>> %timeit list(flatten(L)) # Josh Lee - https://stackoverflow.com/a/2158522/5393381 107 µs ± 2.99 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) >>> %timeit list(genflat(L, list)) # Alex Martelli - https://stackoverflow.com/a/2159079/5393381 23.1 µs ± 710 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

Soy el autor de la librería iteration_utilities .

Fue divertido tratar de crear una función que pudiera aplanar la lista irregular en Python, pero, por supuesto, para eso es Python (para que la progtwigción sea divertida). El siguiente generador funciona bastante bien con algunas advertencias:

 def flatten(iterable): try: for item in iterable: yield from flatten(item) except TypeError: yield iterable 

Acoplará los tipos de datos que querrá dejar solos (como los objetos bytearray , bytes y str ). Además, el código se basa en el hecho de que solicitar un iterador de un no iterable genera un TypeError .

 >>> L = [[[1, 2, 3], [4, 5]], 6] >>> def flatten(iterable): try: for item in iterable: yield from flatten(item) except TypeError: yield iterable >>> list(flatten(L)) [1, 2, 3, 4, 5, 6] >>> 

Editar:

No estoy de acuerdo con la implementación anterior. El problema es que no debe poder aplanar algo que no es un iterable. Es confuso y da la impresión equivocada del argumento.

 >>> list(flatten(123)) [123] >>> 

El siguiente generador es casi el mismo que el primero, pero no tiene el problema de intentar aplanar un objeto no iterable. Falla como uno esperaría cuando se le da un argumento inapropiado.

 def flatten(iterable): for item in iterable: try: yield from flatten(item) except TypeError: yield item 

La prueba del generador funciona bien con la lista que se proporcionó. Sin embargo, el nuevo código generará un TypeError cuando se le dé un objeto no iterable. A continuación se muestran ejemplos del nuevo comportamiento.

 >>> L = [[[1, 2, 3], [4, 5]], 6] >>> list(flatten(L)) [1, 2, 3, 4, 5, 6] >>> list(flatten(123)) Traceback (most recent call last): File "", line 1, in  list(flatten(123)) File "", line 2, in flatten for item in iterable: TypeError: 'int' object is not iterable >>> 

Prefiero respuestas simples. No hay generadores. No hay límites de recursión o recursión. Sólo iteración:

 def flatten(TheList): listIsNested = True while listIsNested: #outer loop keepChecking = False Temp = [] for element in TheList: #inner loop if isinstance(element,list): Temp.extend(element) keepChecking = True else: Temp.append(element) listIsNested = keepChecking #determine if outer loop exits TheList = Temp[:] return TheList 

Esto funciona con dos listas: un bucle for interno y un bucle while externo.

El bucle for interno se repite en la lista. Si encuentra un elemento de lista, (1) usa list.extend () para aplanar el nivel de anidamiento de esa parte uno y (2) cambia keepChecking a True. keepchecking se utiliza para controlar el bucle while externo. Si el bucle externo se establece en verdadero, activa el bucle interno para otra pasada.

Esos pases siguen ocurriendo hasta que no se encuentran más listas anidadas. Cuando finalmente se produce un pase donde no se encuentra ninguno, keepChecking nunca se desvía a verdadero, lo que significa que listIsNested permanece falso y el bucle while externo sale.

La lista aplanada se devuelve.

Prueba de funcionamiento

 flatten([1,2,3,4,[100,200,300,[1000,2000,3000]]]) 

[1, 2, 3, 4, 100, 200, 300, 1000, 2000, 3000]

Aunque se ha seleccionado una respuesta elegante y muy pythonica, presentaría mi solución solo para la revisión:

 def flat(l): ret = [] for i in l: if isinstance(i, list) or isinstance(i, tuple): ret.extend(flat(i)) else: ret.append(i) return ret 

Por favor, dime qué tan bueno o malo es este código?

Aquí hay una función simple que aplana las listas de profundidad arbitraria. Sin recursión, para evitar el desbordamiento de stack.

 from copy import deepcopy def flatten_list(nested_list): """Flatten an arbitrarily nested list, without recursion (to avoid stack overflows). Returns a new list, the original list is unchanged. >> list(flatten_list([1, 2, 3, [4], [], [[[[[[[[[5]]]]]]]]]])) [1, 2, 3, 4, 5] >> list(flatten_list([[1, 2], 3])) [1, 2, 3] """ nested_list = deepcopy(nested_list) while nested_list: sublist = nested_list.pop(0) if isinstance(sublist, list): nested_list = sublist + nested_list else: yield sublist 

Aquí está la implementación compiler.ast.flatten en 2.7.5:

 def flatten(seq): l = [] for elt in seq: t = type(elt) if t is tuple or t is list: for elt2 in flatten(elt): l.append(elt2) else: l.append(elt) return l 

Hay métodos mejores y más rápidos (si has llegado hasta aquí, ya los has visto)

También tenga en cuenta:

En desuso desde la versión 2.6: el paquete del comstackdor se ha eliminado en Python 3.

Me sorprende que nadie haya pensado en esto. Maldita recursión no recibo las respuestas recursivas que hicieron las personas avanzadas aquí. De todos modos aquí está mi bash de esto. advertencia es que es muy específico para el caso de uso del OP

 import re L = [[[1, 2, 3], [4, 5]], 6] flattened_list = re.sub("[\[\]]", "", str(L)).replace(" ", "").split(",") new_list = list(map(int, flattened_list)) print(new_list) 

salida:

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

No revisé todas las respuestas ya disponibles aquí, pero aquí hay un resumen que se me ocurrió, tomando prestado de la forma en que Lisp procesa la primera y la lista de descanso.

 def flatten(l): return flatten(l[0]) + (flatten(l[1:]) if len(l) > 1 else []) if type(l) is list else [l] 

Aquí hay un caso simple y uno no tan simple:

 >>> flatten([1,[2,3],4]) [1, 2, 3, 4] >>> flatten([1, [2, 3], 4, [5, [6, {'name': 'some_name', 'age':30}, 7]], [8, 9, [10, [11, [12, [13, {'some', 'set'}, 14, [15, 'some_string'], 16], 17, 18], 19], 20], 21, 22, [23, 24], 25], 26, 27, 28, 29, 30]) [1, 2, 3, 4, 5, 6, {'age': 30, 'name': 'some_name'}, 7, 8, 9, 10, 11, 12, 13, set(['set', 'some']), 14, 15, 'some_string', 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30] >>> 

totalmente intrincado, pero creo que funcionaría (dependiendo de tu tipo de datos)

 flat_list = ast.literal_eval("[%s]"%re.sub("[\[\]]","",str(the_list))) 

Aquí hay otro enfoque de py2, no estoy seguro si es el más rápido o el más elegante ni el más seguro …

 from collections import Iterable from itertools import imap, repeat, chain def flat(seqs, ignore=(int, long, float, basestring)): return repeat(seqs, 1) if any(imap(isinstance, repeat(seqs), ignore)) or not isinstance(seqs, Iterable) else chain.from_iterable(imap(flat, seqs)) 

Puede ignorar cualquier tipo específico (o derivado) que le gustaría, devuelve un iterador, por lo que puede convertirlo en cualquier contenedor específico como lista, tupla, dict o simplemente consumirlo para reducir el espacio de memoria, para bien o para mal. puede manejar objetos iniciales no iterables como int …

Tenga en cuenta que la mayor parte del trabajo pesado se realiza en C, ya que por lo que sé cómo se implementan sus herramientas, por lo que si bien es recursivo, AFAIK no está limitado por la profundidad de recursión de python, ya que las llamadas a funciones están ocurriendo en C, aunque esto no significa que esté limitado por la memoria, especialmente en OS X, donde su tamaño de stack tiene un límite estricto a partir de hoy (OS X Mavericks) …

hay un enfoque un poco más rápido, pero un método menos portátil, solo utilícelo si puede asumir que los elementos base de la entrada pueden determinarse explícitamente de lo contrario, obtendrá una recursión infinita, y OS X con su tamaño de stack limitado, lanzar una falla de segmentación bastante rápido …

 def flat(seqs, ignore={int, long, float, str, unicode}): return repeat(seqs, 1) if type(seqs) in ignore or not isinstance(seqs, Iterable) else chain.from_iterable(imap(flat, seqs)) 

aquí estamos usando conjuntos para verificar el tipo, por lo que se requiere O (1) vs O (número de tipos) para verificar si un elemento debe ignorarse o no, aunque, por supuesto, cualquier valor con el tipo derivado de los tipos ignorados declarados fallará , esta es la razón por la que usa str , unicode , así que utilízalo con precaución …

pruebas:

 import random def test_flat(test_size=2000): def increase_depth(value, depth=1): for func in xrange(depth): value = repeat(value, 1) return value def random_sub_chaining(nested_values): for values in nested_values: yield chain((values,), chain.from_iterable(imap(next, repeat(nested_values, random.randint(1, 10))))) expected_values = zip(xrange(test_size), imap(str, xrange(test_size))) nested_values = random_sub_chaining((increase_depth(value, depth) for depth, value in enumerate(expected_values))) assert not any(imap(cmp, chain.from_iterable(expected_values), flat(chain(((),), nested_values, ((),))))) >>> test_flat() >>> list(flat([[[1, 2, 3], [4, 5]], 6])) [1, 2, 3, 4, 5, 6] >>> $ uname -a Darwin Samys-MacBook-Pro.local 13.3.0 Darwin Kernel Version 13.3.0: Tue Jun 3 21:27:35 PDT 2014; root:xnu-2422.110.17~1/RELEASE_X86_64 x86_64 $ python --version Python 2.7.5 

Usando itertools.chain :

 import itertools from collections import Iterable def list_flatten(lst): flat_lst = [] for item in itertools.chain(lst): if isinstance(item, Iterable): item = list_flatten(item) flat_lst.extend(item) else: flat_lst.append(item) return flat_lst 

O sin encadenar:

 def flatten(q, final): if not q: return if isinstance(q, list): if not isinstance(q[0], list): final.append(q[0]) else: flatten(q[0], final) flatten(q[1:], final) else: final.append(q) 

Utilicé recursivo para resolver la lista anidada con cualquier profundidad.

 def combine_nlist(nlist,init=0,combiner=lambda x,y: x+y): ''' apply function: combiner to a nested list element by element(treated as flatten list) ''' current_value=init for each_item in nlist: if isinstance(each_item,list): current_value =combine_nlist(each_item,current_value,combiner) else: current_value = combiner(current_value,each_item) return current_value 

Entonces, después de definir la función combine_nlist, es fácil usar esta función para hacer planos. O puedes combinarlo en una función. Me gusta mi solución porque se puede aplicar a cualquier lista anidada.

 def flatten_nlist(nlist): return combine_nlist(nlist,[],lambda x,y:x+[y]) 

resultado

 In [379]: flatten_nlist([1,2,3,[4,5],[6],[[[7],8],9],10]) Out[379]: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 

La forma más sencilla es utilizar la biblioteca de morph utilizando pip install morph .

El código es:

 import morph list = [[[1, 2, 3], [4, 5]], 6] flattened_list = morph.flatten(list) # returns [1, 2, 3, 4, 5, 6] 

Soy consciente de que ya hay muchas respuestas asombrosas, pero quería agregar una respuesta que use el método de progtwigción funcional para resolver la pregunta. En esta respuesta hago uso de la doble recursión:

 def flatten_list(seq): if not seq: return [] elif isinstance(seq[0],list): return (flatten_list(seq[0])+flatten_list(seq[1:])) else: return [seq[0]]+flatten_list(seq[1:]) print(flatten_list([1,2,[3,[4],5],[6,7]])) 

salida:

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

No estoy seguro de si esto es necesariamente más rápido o más efectivo, pero esto es lo que hago:

 def flatten(lst): return eval('[' + str(lst).replace('[', '').replace(']', '') + ']') L = [[[1, 2, 3], [4, 5]], 6] print(flatten(L)) 

La función de flatten aquí convierte la lista en una cadena, quita todos los corchetes, vuelve a colocar los corchetes en los extremos y los convierte en una lista.

Aunque, si supiera que tendría corchetes en su lista en cadenas, como [[1, 2], "[3, 4] and [5]"] , tendría que hacer otra cosa.

Cuando intente responder a una pregunta de este tipo, realmente necesita dar las limitaciones del código que propone como solución. Si solo se tratara de actuaciones, no me importaría demasiado, pero la mayoría de los códigos propuestos como solución (incluida la respuesta aceptada) no logran aplanar ninguna lista que tenga una profundidad superior a 1000.

Cuando digo la mayoría de los códigos, me refiero a todos los códigos que usan cualquier forma de recursión (o que llaman una función de biblioteca estándar que es recursiva). Todos estos códigos fallan porque para cada una de las llamadas recursivas realizadas, la stack (llamada) crece en una unidad, y la stack de llamadas python (predeterminada) tiene un tamaño de 1000.

Si no está muy familiarizado con la stack de llamadas, tal vez le sirva de ayuda (de lo contrario, puede desplazarse hasta la Implementación ).

Tamaño de stack de llamadas y progtwigción recursiva (analogía de mazmorras)

Encontrar el tesoro y salir.

Imagina que entras en una enorme mazmorra con habitaciones numeradas , en busca de un tesoro. No conoces el lugar, pero tienes algunas indicaciones sobre cómo encontrar el tesoro. Cada indicación es un acertijo (la dificultad varía, pero no se puede predecir qué tan difícil será). Decides pensar un poco en una estrategia para ahorrar tiempo, haces dos observaciones:

  1. Es difícil (largo) encontrar el tesoro, ya que tendrás que resolver acertijos (potencialmente difíciles) para llegar allí.
  2. Una vez que haya encontrado el tesoro, volver a la entrada puede ser fácil, solo tiene que usar el mismo camino en la otra dirección (aunque esto necesita un poco de memoria para recordar su camino).

Al entrar en la mazmorra, se nota un pequeño cuaderno aquí. Decide utilizarlo para anotar cada habitación que sale después de resolver un enigma (cuando ingresa a una nueva habitación), de esta manera podrá regresar a la entrada. Esa es una idea genial, ni siquiera gastarás un centavo implementando tu estrategia.

Entras en la mazmorra y resuelves con gran éxito los primeros 1001 acertijos, pero aquí viene algo que no habías planeado, no te queda espacio en el cuaderno que tomaste prestado. Decides abandonar tu búsqueda ya que prefieres no tener el tesoro que perderte para siempre dentro de la mazmorra (lo cual parece inteligente).

Ejecutando un progtwig recursivo

Básicamente, es exactamente lo mismo que encontrar el tesoro. La mazmorra es la memoria de la computadora , tu objective ahora no es encontrar un tesoro sino calcular una función (encontrar f (x) para una x dada). Las indicaciones son simplemente sub-rutinas que te ayudarán a resolver f (x) . Su estrategia es la misma que la estrategia de stack de llamadas , la libreta es la stack, las salas son las direcciones de retorno de las funciones:

 x = ["over here", "am", "I"] y = sorted(x) # You're about to enter a room named `sorted`, note down the current room address here so you can return back: 0x4004f4 (that room address looks weird) # Seems like you went back from your quest using the return address 0x4004f4 # Let's see what you've collected print(' '.join(y)) 

The problem you encountered in the dungeon will be the same here, the call stack has a finite size (here 1000) and therefore, if you enter too many functions without returning back then you’ll fill the call stack and have an error that look like “Dear adventurer, I’m very sorry but your notebook is full” : RecursionError: maximum recursion depth exceeded . Note that you don’t need recursion to fill the call stack, but it’s very unlikely that a non-recursive program call 1000 functions without ever returning. It’s important to also understand that once you returned from a function, the call stack is freed from the address used (hence the name “stack”, return address are pushed in before entering a function and pulled out when returning). In the special case of a simple recursion (a function f that call itself once — over and over –) you will enter f over and over until the computation is finished (until the treasure is found) and return from f until you go back to the place where you called f in the first place. The call stack will never be freed from anything until the end where it will be freed from all return addresses one after the other.

How to avoid this issue?

That’s actually pretty simple: “don’t use recursion if you don’t know how deep it can go”. That’s not always true as in some cases, Tail Call recursion can be Optimized (TCO) . But in python, this is not the case, and even “well written” recursive function will not optimize stack use. There is an interesting post from Guido about this question: Tail Recursion Elimination .

There is a technique that you can use to make any recursive function iterative, this technique we could call bring your own notebook . For example, in our particular case we simply are exploring a list, entering a room is equivalent to entering a sublist, the question you should ask yourself is how can I get back from a list to its parent list? The answer is not that complex, repeat the following until the stack is empty:

  1. push the current list address and index in a stack when entering a new sublist (note that a list address+index is also an address, therefore we just use the exact same technique used by the call stack);
  2. every time an item is found, yield it (or add them in a list);
  3. once a list is fully explored, go back to the parent list using the stack return address (and index ) .

Also note that this is equivalent to a DFS in a tree where some nodes are sublists A = [1, 2] and some are simple items: 0, 1, 2, 3, 4 (for L = [0, [1,2], 3, 4] ). The tree looks like this:

  L | ------------------- | | | | 0 --A-- 3 4 | | 1 2 

The DFS traversal pre-order is: L, 0, A, 1, 2, 3, 4. Remember, in order to implement an iterative DFS you also “need” a stack. The implementation I proposed before result in having the following states (for the stack and the flat_list ):

 init.: stack=[(L, 0)] **0**: stack=[(L, 0)], flat_list=[0] **A**: stack=[(L, 1), (A, 0)], flat_list=[0] **1**: stack=[(L, 1), (A, 0)], flat_list=[0, 1] **2**: stack=[(L, 1), (A, 1)], flat_list=[0, 1, 2] **3**: stack=[(L, 2)], flat_list=[0, 1, 2, 3] **3**: stack=[(L, 3)], flat_list=[0, 1, 2, 3, 4] return: stack=[], flat_list=[0, 1, 2, 3, 4] 

In this example, the stack maximum size is 2, because the input list (and therefore the tree) have depth 2.

Implementación

For the implementation, in python you can simplify a little bit by using iterators instead of simple lists. References to the (sub)iterators will be used to store sublists return addresses (instead of having both the list address and the index). This is not a big difference but I feel this is more readable (and also a bit faster):

 def flatten(iterable): return list(items_from(iterable)) def items_from(iterable): cursor_stack = [iter(iterable)] while cursor_stack: sub_iterable = cursor_stack[-1] try: item = next(sub_iterable) except StopIteration: # post-order cursor_stack.pop() continue if is_list_like(item): # pre-order cursor_stack.append(iter(item)) elif item is not None: yield item # in-order def is_list_like(item): return isinstance(item, list) 

Also, notice that in is_list_like I have isinstance(item, list) , which could be changed to handle more input types, here I just wanted to have the simplest version where (iterable) is just a list. But you could also do that:

 def is_list_like(item): try: iter(item) return not isinstance(item, str) # strings are not lists (hmm...) except TypeError: return False 

This considers strings as “simple items” and therefore flatten_iter([["test", "a"], "b]) will return ["test", "a", "b"] and not ["t", "e", "s", "t", "a", "b"] . Remark that in that case, iter(item) is called twice on each item, let’s pretend it’s an exercise for the reader to make this cleaner.

Testing and remarks on other implementations

In the end, remember that you can’t print a infinitely nested list L using print(L) because internally it will use recursive calls to __repr__ ( RecursionError: maximum recursion depth exceeded while getting the repr of an object ). For the same reason, solutions to flatten involving str will fail with the same error message.

If you need to test your solution, you can use this function to generate a simple nested list:

 def build_deep_list(depth): """Returns a list of the form $l_{depth} = [depth-1, l_{depth-1}]$ with $depth > 1$ and $l_0 = [0]$. """ sub_list = [0] for d in range(1, depth): sub_list = [d, sub_list] return sub_list 

Which gives: build_deep_list(5) >>> [4, [3, [2, [1, [0]]]]] .

This is a simple implement of flatten on python2

 flatten=lambda l: reduce(lambda x,y:x+y,map(flatten,l),[]) if isinstance(l,list) else [l] test=[[1,2,3,[3,4,5],[6,7,[8,9,[10,[11,[12,13,14]]]]]],] print flatten(test) #output [1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14] 

If you like recursion, this might be a solution of interest to you:

 def f(E): if E==[]: return [] elif type(E) != list: return [E] else: a = f(E[0]) b = f(E[1:]) a.extend(b) return a 

I actually adapted this from some practice Scheme code that I had written a while back.

¡Disfrutar!

I’m new to python and come from a lisp background. This is what I came up with (check out the var names for lulz):

 def flatten(lst): if lst: car,*cdr=lst if isinstance(car,(list,tuple)): if cdr: return flatten(car) + flatten(cdr) return flatten(car) if cdr: return [car] + flatten(cdr) return [car] 

Seems to work. Test:

 flatten((1,2,3,(4,5,6,(7,8,(((1,2))))))) 

returns:

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

I don’t see anything like this posted around here and just got here from a closed question on the same subject, but why not just do something like this(if you know the type of the list you want to split):

 >>> a = [1, 2, 3, 5, 10, [1, 25, 11, [1, 0]]] >>> g = str(a).replace('[', '').replace(']', '') >>> b = [int(x) for x in g.split(',') if x.strip()] 

You would need to know the type of the elements but I think this can be generalised and in terms of speed I think it would be faster.

Without using any library:

 def flat(l): def _flat(l, r): if type(l) is not list: r.append(l) else: for i in l: r = r + flat(i) return r return _flat(l, []) # example test = [[1], [[2]], [3], [['a','b','c'] , [['z','x','y']], ['d','f','g']], 4] print flat(test) # prints [1, 2, 3, 'a', 'b', 'c', 'z', 'x', 'y', 'd', 'f', 'g', 4] 

Shamelessly taken from my own answer to another question .

This function

  • Does not use isinstance , because it’s evil and breaks duck typing.
  • Uses reduce recursively. There has to be an answer using reduce .
  • Works with arbitrary nested-lists whose elements are either nested-lists, or non-nested lists of atoms, or atoms (subjected to recursion limit).
  • Does not LBYL.
  • But not with nested-lists that contain strings as atoms.

Code below:

 def flattener(left, right): try: res = reduce(flattener, right, left) except TypeError: left.append(right) res = left return res def flatten(seq): return reduce(flattener, seq, []) >>> nested_list = [0, [1], [[[[2]]]], [3, [], [4, 5]], [6, [7, 8], 9, [[[]], 10, []]], 11, [], [], [12]] >>> flatten(nested_list) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]