Aplatir une liste irrégulière de listes

Question

Oui, je sais que ce sujet a déjà été abordé ( aquí , aquí , aquí , aquí ), mais pour autant que je sache, toutes les solutions, sauf une, échouent sur une liste comme celle-ci :

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

Lorsque la sortie souhaitée est

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

Ou, mieux encore, un itérateur. La seule solution que j'ai vue qui fonctionne pour une imbrication arbitraire se trouve dans cette question :

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)

Est-ce le meilleur modèle ? Ai-je oublié quelque chose ? Y a-t-il des problèmes ?

Answer 1

L'utilisation de fonctions de générateur peut rendre votre exemple un peu plus facile à lire et probablement améliorer les performances.

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

J'ai utilisé le Iterable ABC ajouté en 2.6.

Python 3

Dans Python 3, la fonction basestring n'est plus, mais vous pouvez utiliser un tuple de str y bytes pour obtenir le même effet à cet endroit.

El yield from L'opérateur renvoie un élément d'un générateur, un par un. Ce site syntaxe pour déléguer à un sous-générateur a été ajouté en 3.3

from collections.abc import Iterable

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

Answer 2

Ma solution :

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 peu plus concis, mais à peu près pareil.

Answer 3

Vous pourriez simplement utiliser la fonction flatten dans le fichier compiler.ast module.

>>> from compiler.ast import flatten
>>> flatten([0, [1, 2], [3, 4, [5, 6]], 7])
[0, 1, 2, 3, 4, 5, 6, 7]

Answer 4

Version génératrice de la solution non-récursive de @unutbu, comme demandé par @Andrew dans un commentaire :

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

Version légèrement simplifiée de ce générateur :

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)

Answer 5

Cette version de flatten évite la limite de récursion de python (et fonctionne donc avec des itérables imbriqués et arbitrairement profonds). C'est un générateur qui peut gérer des chaînes de caractères et des itérables arbitraires (même infinis).

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

Voici quelques exemples démontrant son utilisation :

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]

Bien que flatten peut gérer les générateurs infinis, mais pas l'imbrication infinie :

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

print(list(IT.islice(flatten(infinitely_nested()), 10)))
# hangs