Acoplar una lista irregular de listas

440

Sí, sé que este tema se ha cubierto antes ( aquí , aquí , aquí , aquí ), pero que yo sepa, 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 tal vez 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? Cualquier problema?

telliott99
fuente
16
El hecho de que haya tantas respuestas y tanta acción sobre esta pregunta realmente sugiere que esta debería ser una función incorporada en algún lugar, ¿verdad? Es especialmente malo que compiler.ast haya sido eliminado de Python 3.0
Mittenchops
3
Yo diría que lo que Python realmente necesita es una recursión ininterrumpida en lugar de otro incorporado.
arcilla
2
@Mittenchops: totalmente en desacuerdo, el hecho de que las personas que trabajan con API obviamente malas / estructuras de datos demasiado complicadas (solo una nota: lists pretenden ser homogéneas) no significa que sea una falla de Python y que necesitamos una construcción para tal tarea
Azat Ibrakov
1
Si puede permitirse agregar un paquete a su proyecto, supongo que la solución more_itertools.collapse lo hará mejor. De esta respuesta: stackoverflow.com/a/40938883/3844376
viddik13

Respuestas:

382

El uso de 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 añadió en 2,6.

Python 3

En Python 3, basestringya no existe, pero puedes usar una tupla de stry bytesobtener el mismo efecto allí.

El yield fromoperador devuelve un artículo de un generador uno a la vez. Esta sintaxis para delegar en 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
Cristian
fuente
66
De todas las sugerencias en esta página, esta es la única que aplanó esta lista l = ([[chr(i),chr(i-32)] for i in xrange(ord('a'), ord('z')+1)] + range(0,9))en un instante cuando hice esto list(flatten(l)). ¡Todos los demás comenzarían a trabajar y tardarían para siempre!
nemesisfixx
77
Esto también aplana los diccionarios. Tal vez quieres usar en collections.Sequencelugar de collections.Iteratable?
josch
1
Esto no funciona con cosas que no son listas inicialmente, por ejemplo for i in flatten(42): print (i). Esto podría solucionarse moviendo la isinstancecláusula for el-test y la cláusula else fuera del bucle. (Entonces podría arrojarle cualquier cosa, y se haría una lista aplanada)
RolKau
66
Para Python 3.7, el uso collections.Iterableestá en desuso. Usar en su collections.abc.Iterablelugar.
dawg
55
De hecho, la recursión nunca es necesaria. En este caso específico, usar la recursión no es la mejor solución, ya que se bloqueará en listas profundamente anidadas (profundidad> 1000). Pero si no tiene como objetivo tener algo seguro, entonces sí, las funciones recursivas son mejores, ya que son mucho más fáciles de leer / escribir.
cglacet
50

Mi solución:

import collections


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.

Josh Lee
fuente
55
Puede hacer esto sin importar nada si solo try: iter(x)prueba si es iterable ... Pero no creo que tener que importar un módulo stdlib sea una desventaja que vale la pena evitar.
abarnert
8
Vale la pena señalar que esta solución solo funciona si todos los elementos son de tipoint
alfasin
1
Podría hacerlo más conciso, def flatten(x): return [a for i in x for a in flatten(i)] if isinstance(x, collections.Iterable) else [x]pero la legibilidad podría ser subjetiva aquí.
Cero
44
esto no funciona en cadenas porque las cadenas también son iterables. Reemplace la condición conif isinstance(x, collections.Iterable) and not isinstance(x, basestring)
aandis
reemplazar collections.Iterableconlist
noobninja
36

Generador que utiliza la recursividad y la 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]
dansalmo
fuente
1
Gracias, eso funciona bien para Python 3. Para 2.x se necesita lo anterior: for i in flatten(item): yield i
dansalmo
list (flatten ([['' X '],' Y '])) falla en la variante 2.X
sten
@ user1019129 mira mi comentario sobre el tuyo
dansalmo
sí, falla con el ciclo ... creo que porque una cadena también es una "matriz" de caracteres
sten
35

Versión del generador de la solución no recursiva de @unutbu, según lo solicitado por @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)
Alex Martelli
fuente
Es un recorrido de preorden del árbol formado por las listas anidadas. solo se devuelven las hojas. Tenga en cuenta que esta implementación consumirá la estructura de datos original, para bien o para mal. Podría ser divertido escribir uno que conserve el árbol original, pero que no tenga que copiar las entradas de la lista.
Andrew Wagner el
66
Creo que debe probar las cadenas, por ejemplo, agregue "y no isinstance (l [0], basetring)" como en la solución de Cristian. De lo contrario, obtienes un bucle infinito alrededor de l [0: 1] = l [0]
c-urchin
Este es un buen ejemplo de cómo hacer un generador, pero como menciona c-urchin, el algoritmo falla cuando la secuencia contiene cadenas.
Daniel 'Dang' Griffith
28

Aquí está mi versión funcional de aplanar recursivo que maneja tuplas y 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]
samplebias
fuente
1
gran solución, sin embargo, sería mucho más útil si se ha añadido algún comentario para describir lo que e, a, nse refiere a
Kristof Pal
2
@WolfgangKuehne: Trata argsde n, intermediate(o la más corta mid, o si lo prefiere element) de ay resultpara e, por lo que:flatten = lambda *args: (result for mid in args for result in (flatten(*mid) if isinstance(mid, (tuple, list)) else (mid,)))
En pausa hasta nuevo aviso.
Esto es significativamente más rápido que compiler.ast.flatten. Gran código compacto, funciona para cualquier tipo de objeto (creo).
bcdan
Wow, esta debería ser la respuesta más votada y aceptada ... ¡funciona de maravilla!
U10-Adelante
27

Esta versión de flattenevita el límite de recursión de Python (y, por lo tanto, funciona con iterables anidados arbitrariamente profundos). Es un generador que puede manejar cadenas e iterables arbitrarios (incluso 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, (str, bytes)):
            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 range(ord('a'), ord('z')+1)] + list(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 flattenpuede manejar generadores infinitos, no puede manejar anidamiento infinito:

def infinitely_nested():
    while True:
        yield IT.chain(infinitely_nested(), IT.repeat(1))

print(list(IT.islice(flatten(infinitely_nested()), 10)))
# hangs
unutbu
fuente
1
¿Hay consenso sobre si utilizar ABC Iterable o ABC Sequence?
wim
sets, dicts, deques, listiterators, generators,, Filehandles y clases personalizadas con __iter__definido son todas las instancias de collections.Iterable, pero no collections.Sequence. El resultado de aplanar a dictes un poco dudoso, pero por lo demás, creo que collections.Iterablees un mejor valor predeterminado que collections.Sequence. Definitivamente es el más liberal.
unutbu
@wim: Un problema con el uso collections.Iterablees que esto incluye generadores infinitos. He cambiado mi respuesta manejar este caso.
unutbu
1
Esto no parece funcionar para los ejemplos tercero y cuarto. Se tira StopIteration. Además, parece que while True: first = next(remainder) podría ser reemplazado por for first in remainder:.
Georgy
@ Georgia, esto podría solucionarse encapsulando el cuerpo de aplanar en a try-except StopIteration block.
Baduker
12

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 sintaxis anidada y luego convierte el resultado nuevamente en una lista (aplanada).

arcilla
fuente
Si intenta generalizar esto a algo distinto de los valores int, será divertido, por ejemplo, [['C=64', 'APPLE ]['], ['Amiga', 'Mac', 'ST']]:) Por otro lado, dada una lista que se contiene, funcionará un poco mejor que las otras respuestas, generando un excepción en lugar de simplemente hacer un bucle hasta que se quede sin memoria / recurrir hasta agotar la pila ...
abarnert
El mensaje original era sobre aplanar una lista de enteros. Si solo cambia la comprensión de la lista a d = [x para x en c], debería funcionar bien para su muestra.
arcilla
Primero, [x for x in c]es solo una forma lenta y detallada de hacer una copia c, entonces ¿por qué harías eso? En segundo lugar, su código claramente se convertirá 'APPLE ]['en 'APPLE ', porque no maneja las comillas, solo asume que los corchetes son corchetes de lista.
abarnert
¡Decir ah! La forma en que su comentario fue formateado en mi computadora, ni siquiera me di cuenta de que se suponía que era Apple II como aparecía en las computadoras viejas. En cualquier caso, mi respuesta a ambas preguntas es que este ejercicio, para mí, es simplemente un experimento para encontrar una solución creativa para aplanar una lista. No estoy seguro de que lo generalice para aplanar todas las listas.
arcilla
Solo necesitas arr_str = str(arr)y luego [int(s) for s in re.findall(r'\d+', arr_str)]realmente. Ver github.com/jorgeorpinel/flatten_nested_lists/blob/master/…
Jorge Orpinel
10
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
kev
fuente
8

Puede usar deepflattendesde el paquete de terceros iteration_utilities:

>>> 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, envolviéndolo listo usándolo en un bucle). Internamente utiliza un enfoque iterativo en lugar de un enfoque recursivo y está escrito como una extensión C, por lo que puede 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 iteration_utilitiesbiblioteca.

MSeifert
fuente
7

Fue divertido intentar crear una función que pudiera aplanar la lista irregular en Python, pero, por supuesto, para eso está Python (hacer que la programació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

Se aplanará tipos de datos que es posible que desee dejar en paz (como bytearray, bytesy strobjetos). Además, el código se basa en el hecho de que solicitar un iterador de un no iterable aumenta a 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 deberías poder aplanar algo que no sea 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 cabría esperar cuando se le da un argumento inapropiado.

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

Probar el generador funciona bien con la lista que se proporcionó. Sin embargo, el nuevo código generará un TypeErrorcuando se le da 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 "<pyshell#32>", line 1, in <module>
    list(flatten(123))
  File "<pyshell#27>", line 2, in flatten
    for item in iterable:
TypeError: 'int' object is not iterable
>>>
Noctis Skytower
fuente
5

Aunque se ha seleccionado una respuesta elegante y muy pitónica, 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 diga qué tan bueno o malo es este código?

Xolve
fuente
1
Uso isinstance(i, (tuple, list)). La inicialización de las variables vacía es una bandera para que se ocupara de estructuras alternativas de código, típicamente por comprensión, generadores, recursividad, etc.
dansalmo
3
return type(l)(ret)también le devolverá el mismo tipo de contenedor que se le pasó. :)
dash-tom-bang
@ dash-tom-bang ¿Puede explicar qué significa en detalle?
Xolve
1
Si pasa una lista, probablemente quiera recuperarla. Si pasa una tupla, probablemente quiera recuperar una tupla. Si pasas en una mezcla de los dos, obtendrás lo que sea que fuera el cerramiento exterior.
dash-tom-bang
4

Prefiero respuestas simples. No hay generadores. Sin recursión o límites de recursión. Solo 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 itera a través de la lista. Si encuentra un elemento de lista, (1) usa list.extend () para aplanar esa parte de un nivel de anidamiento 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 otro pase.

Esos pases continúan sucediendo hasta que no se encuentren más listas anidadas. Cuando finalmente se produce un pase donde no se encuentra ninguno, keepChecking nunca se dispara a verdadero, lo que significa que listIsNested permanece falso y el ciclo 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]

arcilla
fuente
Me gusta lo simple también. Sin embargo, en este caso, itera sobre la lista tantas veces como haya anidaciones o niveles. Podría ser costoso.
telliott99
@ telliott99: Tienes razón si tus listas son realmente grandes y / o están anidadas a grandes profundidades. Sin embargo, si ese no es el caso, entonces la solución más simple funciona igual de bien y sin la magia profunda de algunas de las otras respuestas. Hay un lugar para las comprensiones de generador recursivo en varias etapas, pero no estoy convencido de que sea aquí donde se mire primero. (Supongo que usted sabe dónde me quedo en el "peor es mejor" debate.)
arcilla
@ telliott99: O para decirlo de otra manera, no tendrás que "intentar Grok" mi solución. Si el rendimiento no es un cuello de botella, ¿qué es lo que más te importa como programador?
arcilla
Las soluciones más simples tienen menos lógica. La recursión es una construcción de programación bastante fundamental con la que cualquier persona que se considere un programador debería sentirse completamente cómodo. Los generadores son muy parecidos a Python Way y (junto con las comprensiones) son algo que cualquier programador profesional de Python debería asimilar instantáneamente.
dash-tom-bang
1
Estoy de acuerdo con la recursividad. Cuando escribí mi respuesta, Python todavía rompió la recursión a 1000 ciclos. ¿Han cambiado esto? En cuanto a ser un programador profesional de Python, no lo soy. Además, me imagino que muchas personas que programan en Python no lo hacen a tiempo completo.
arcilla
4

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

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
Wilfred Hughes
fuente
¡Si! Muy similar a mi código en github.com/jorgeorpinel/flatten_nested_lists/blob/master/…
Jorge Orpinel
3

Me sorprende que nadie haya pensado en esto. Maldita recursión No obtengo las respuestas recursivas que hicieron las personas avanzadas aquí. de todos modos aquí está mi intento de esto. La advertencia es que es muy específica 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]
Sión
fuente
3

No revisé todas las respuestas ya disponibles aquí, pero aquí hay una frase que se me ocurrió, tomando prestado de la forma en que Lisp procesó primero y de 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]
>>> 
Shreyas
fuente
No es un trazador de líneas. No importa cuánto intente encajarlo en uno, def foo():hay una línea separada. Además, esto es muy ilegible.
cs95
De-one-line-ified el código, e hice algunas refactorizaciones adicionales. (la edición está pendiente de revisión por pares mientras escribo esto) Este método en particular me pareció muy legible, aunque el código original necesitaba un poco de refactorización.
Emilio M Bumachar
3

Al intentar 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 llaman a una función de biblioteca estándar que es recursiva). Todos estos códigos fallan porque por cada llamada recursiva realizada, la pila (llamada) crece en una unidad, y la pila de llamadas python (predeterminada) tiene un tamaño de 1000.

Si no está demasiado familiarizado con la pila de llamadas, quizás lo siguiente le ayude (de lo contrario, puede desplazarse a la Implementación ).

Tamaño de la pila de llamadas y programación recursiva (analogía de mazmorra)

Encontrar el tesoro y salir

Imagina que entras en una mazmorra enorme con habitaciones numeradas , buscando un tesoro. No conoce el lugar, pero tiene 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 encuentre el tesoro, regresar 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, ves un pequeño cuaderno aquí. Decide usarlo para escribir cada habitación que salga después de resolver un acertijo (al ingresar a una nueva habitación), de esta manera podrá regresar a la entrada. Esa es una idea genial, ni siquiera gastará un centavo implementando su estrategia.

Entras al calabozo, resolviendo 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 (eso parece inteligente).

Ejecutando un programa recursivo

Básicamente, es exactamente lo mismo que encontrar el tesoro. El calabozo es la memoria de la computadora , su objetivo ahora no es encontrar un tesoro sino calcular alguna función (encontrar f (x) para una x dada ). Las indicaciones simplemente son subrutinas que lo ayudarán a resolver f (x) . Su estrategia es la misma que la estrategia de la pila de llamadas , el cuaderno es la pila, 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))

El problema que encontró en la mazmorra será el mismo aquí, la pila de llamadas tiene un tamaño finito (aquí 1000) y, por lo tanto, si ingresa demasiadas funciones sin regresar, completará la pila de llamadas y tendrá un error que se verá como "Querido aventurero, lo siento mucho, pero su cuaderno está lleno" : RecursionError: maximum recursion depth exceeded. Tenga en cuenta que no necesita recursividad para llenar la pila de llamadas, pero es muy poco probable que un programa no recursivo llame a 1000 funciones sin volver nunca. También es importante comprender que una vez que regresó de una función, la pila de llamadas se libera de la dirección utilizada (de ahí el nombre "pila", la dirección de retorno se inserta antes de ingresar una función y se retira al regresar). En el caso especial de una recursión simple (una funciónfque se llama a sí mismo una vez, una y otra vez, entrará funa y otra vez hasta que finalice el cálculo (hasta que se encuentre el tesoro) y regresará fhasta que regrese al lugar donde llamó fen primer lugar. La pila de llamadas nunca se liberará de nada hasta el final, donde se liberará de todas las direcciones de retorno, una tras otra.

¿Cómo evitar este problema?

En realidad, eso es bastante simple: "no uses la recursividad si no sabes qué tan profundo puede llegar". Eso no siempre es cierto, ya que en algunos casos, la recursividad de llamadas de cola se puede optimizar (TCO) . Pero en Python, este no es el caso, e incluso la función recursiva "bien escrita" no optimizará el uso de la pila. Hay una publicación interesante de Guido sobre esta pregunta: Eliminación de recursión de cola .

Hay una técnica que puede usar para hacer que cualquier función recursiva sea iterativa, esta técnica podríamos llamar traer su propio cuaderno . Por ejemplo, en nuestro caso particular simplemente estamos explorando una lista, ingresar a una habitación es equivalente a ingresar una sublista, la pregunta que debe hacerse es cómo puedo volver de una lista a su lista principal. La respuesta no es tan compleja, repita lo siguiente hasta que stackesté vacío:

  1. empuje la lista actual addressy indexen un stackal ingresar una nueva sublista (tenga en cuenta que una dirección de lista + índice también es una dirección, por lo tanto, solo usamos la misma técnica utilizada por la pila de llamadas);
  2. cada vez que se encuentra un elemento, yield(o agréguelo a una lista);
  3. una vez que se explora por completo una lista, regrese a la lista principal utilizando el stack retorno address(y index) .

También tenga en cuenta que esto es equivalente a un DFS en un árbol donde algunos nodos son sublistas A = [1, 2]y algunos son elementos simples: 0, 1, 2, 3, 4(para L = [0, [1,2], 3, 4]). El árbol se ve así:

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

El preorden transversal de DFS es: L, 0, A, 1, 2, 3, 4. Recuerde, para implementar un DFS iterativo también "necesita" una pila. La implementación que propuse antes da como resultado tener los siguientes estados (para el stacky el 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]

En este ejemplo, el tamaño máximo de la pila es 2, porque la lista de entrada (y, por lo tanto, el árbol) tiene profundidad 2.

Implementación

Para la implementación, en python puede simplificar un poco utilizando iteradores en lugar de listas simples. Las referencias a los (sub) iteradores se utilizarán para almacenar las direcciones de retorno de las sublistas (en lugar de tener tanto la dirección de la lista como el índice). Esto no es una gran diferencia, pero creo que es más legible (y también un poco más rápido):

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)

Además, is_list_liketenga en cuenta que en I have isinstance(item, list), que podría cambiarse para manejar más tipos de entrada, aquí solo quería tener la versión más simple donde (iterable) es solo una lista. Pero también podrías hacer eso:

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

Esto considera las cadenas como "elementos simples" y, por flatten_iter([["test", "a"], "b])lo tanto , regresará ["test", "a", "b"]y no ["t", "e", "s", "t", "a", "b"]. Tenga en cuenta que en ese caso, iter(item)se llama dos veces en cada elemento, supongamos que es un ejercicio para el lector hacer esto más limpio.

Pruebas y comentarios sobre otras implementaciones

Al final, recuerde que usted no puede imprimir una lista infinitamente anidada Lusando print(L), porque internamente se utilizará para llamadas recursivas __repr__( RecursionError: maximum recursion depth exceeded while getting the repr of an object). Por la misma razón, las soluciones a la flattenparticipación strfallarán con el mismo mensaje de error.

Si necesita probar su solución, puede usar esta función para generar una lista anidada simple:

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

Lo que da: build_deep_list(5)>>> [4, [3, [2, [1, [0]]]]].

cglacet
fuente
2

Aquí está la compiler.ast.flattenimplementación 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 compilador se ha eliminado en Python 3.

pradyunsg
fuente
2

totalmente hacky pero creo que funcionaría (dependiendo de su tipo de datos)

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

Solo usa una funcybiblioteca: pip install funcy

import funcy


funcy.flatten([[[[1, 1], 1], 2], 3]) # returns generator
funcy.lflatten([[[[1, 1], 1], 2], 3]) # returns list
ADR
fuente
1
FYI: utiliza una solución recursiva: enlace a la fuente
Georgy
1

Aquí hay otro enfoque de py2, no estoy seguro de 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 desee, devuelve un iterador, por lo que puede convertirlo a cualquier contenedor específico como list, tuple, dict o simplemente consumirlo para reducir la huella 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é, así es como se implementan las herramientas de iterto, por lo tanto, aunque es recursivo, AFAIK no está limitado por la profundidad de recursión de Python ya que las llamadas a funciones están sucediendo en C, aunque esto no significa que esté limitado por la memoria, especialmente en OS X, donde su tamaño de pila tiene un límite estricto a día de hoy (OS X Mavericks) ...

hay un enfoque un poco más rápido, pero un método menos portátil, solo úselo si puede suponer que los elementos base de la entrada se pueden determinar explícitamente de lo contrario, obtendrá una recursión infinita y OS X con su tamaño de pila 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 necesita O (1) vs O (número de tipos) para verificar si un elemento debe ser ignorado 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 está usando str, unicodeasí que úselo 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
Samy Vilar
fuente
1

Sin usar ninguna biblioteca:

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]
alfasin
fuente
1

Utilizando 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)
Saksham Varma
fuente
1

Solía ​​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 aplanar. O puede 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]
Viejo joven
fuente
"lista anidada con cualquier profundidad" no es verdadera. Solo intenta ver: current_value = combiner(current_value,each_item) RecursionError: maximum recursion depth exceeded
cglacet
hmmm, ¿estás tratando de acoplar la lista con más de 1000 capas?
Oldyoung
Por supuesto, ese es el punto central de la discusión sobre las soluciones recursivas vs. iterativas. Si sabe de antemano que la cantidad de capas es <1000, entonces la solución más simple funcionará. Cuando dices "cualquier profundidad", esto incluye una lista con profundidad> 1000.
cglacet
1

La forma más fácil es usar la biblioteca morph usando pip install morph.

El codigo es:

import morph

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

Soy consciente de que ya hay muchas respuestas increíbles, pero quería agregar una respuesta que utilice el método de programación funcional para resolver la pregunta. En esta respuesta, uso 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]
Leo Wahyd
fuente
1

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 flattenfunción aquí convierte la lista en una cadena, saca todos los corchetes, vuelve a colocar los corchetes en los extremos y los convierte nuevamente en una lista.

Sin embargo, si supiera que tendría corchetes en su lista en cadenas, como [[1, 2], "[3, 4] and [5]"], tendría que hacer algo más.

diligar
fuente
Esto no tiene ninguna ventaja sobre la solución simple ya que no puede procesar listas profundas, es decir, "RecursionError: profundidad de recursión máxima excedida al obtener la reproducción de un objeto".
cglacet
1

Esta es una implementación simple de flatten en 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]
Statham
fuente
1

Esto aplanará una lista o diccionario (o una lista de listas o diccionarios de diccionarios, etc.). Se supone que los valores son cadenas y crea una cadena que concatena cada elemento con un argumento separador. Si lo desea, puede usar el separador para dividir el resultado en un objeto de lista después. Utiliza la recursividad si el siguiente valor es una lista o una cadena. Use el argumento clave para saber si desea las claves o los valores (establezca la clave en falso) del objeto del diccionario.

def flatten_obj(n_obj, key=True, my_sep=''):
    my_string = ''
    if type(n_obj) == list:
        for val in n_obj:
            my_sep_setter = my_sep if my_string != '' else ''
            if type(val) == list or type(val) == dict:
                my_string += my_sep_setter + flatten_obj(val, key, my_sep)
            else:
                my_string += my_sep_setter + val
    elif type(n_obj) == dict:
        for k, v in n_obj.items():
            my_sep_setter = my_sep if my_string != '' else ''
            d_val = k if key else v
            if type(v) == list or type(v) == dict:
                my_string += my_sep_setter + flatten_obj(v, key, my_sep)
            else:
                my_string += my_sep_setter + d_val
    elif type(n_obj) == str:
        my_sep_setter = my_sep if my_string != '' else ''
        my_string += my_sep_setter + n_obj
        return my_string
    return my_string

print(flatten_obj(['just', 'a', ['test', 'to', 'try'], 'right', 'now', ['or', 'later', 'today'],
                [{'dictionary_test': 'test'}, {'dictionary_test_two': 'later_today'}, 'my power is 9000']], my_sep=', ')

rendimientos:

just, a, test, to, try, right, now, or, later, today, dictionary_test, dictionary_test_two, my power is 9000
Matt Farguson
fuente
0

Si le gusta la recursividad, esta podría ser una solución de su interés:

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

De hecho, adapté esto de algún código de esquema de práctica que había escrito hace un tiempo.

¡Disfrutar!

inspectorG4dget
fuente
0

Soy nuevo en Python y vengo de un fondo lisp. Esto es lo que se me ocurrió (mira los nombres de var para 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]

Parece funcionar. Prueba:

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

devoluciones:

[1, 2, 3, 4, 5, 6, 7, 8, 1, 2]
Michael Puckett
fuente