Spłaszcz nieregularną listę list

Tak, wiem, że ten temat był już wcześniej omawiany ( tutaj , tutaj , tutaj , tutaj ), ale o ile wiem, wszystkie rozwiązania, z wyjątkiem jednego, zawodzą na takiej liście:

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

Gdzie jest pożądane wyjście

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

A może nawet lepiej, iterator. Jedyne rozwiązanie, jakie widziałem, które działa dla dowolnego zagnieżdżenia, można znaleźć w tym pytaniu :

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)

Czy to najlepszy model? Czy coś przeoczyłem? Jakieś problemy?

Korzystanie z funkcji generatora może sprawić, że twój przykład będzie trochę łatwiejszy do odczytania i prawdopodobnie zwiększy wydajność.

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

Użyłem Iterable ABC dodanego w wersji 2.6.

Python 3

W Pythonie 3 basestringnie ma już, ale możesz użyć krotki stri, bytesaby uzyskać ten sam efekt.

yield fromOperator zwraca element z jednego generatora na raz. Ta składnia delegowania do subgeneratora została dodana w 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

Moje rozwiązanie:

import collections


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

Trochę bardziej zwięzły, ale prawie taki sam.

Generator wykorzystujący rekurencję i pisanie kaczych (zaktualizowany dla 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]

Wersja generatora nierekurencyjnego rozwiązania @ unutbu, zgodnie z żądaniem @Andrew w komentarzu:

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

Nieco uproszczona wersja tego generatora:

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)

Oto moja funkcjonalna wersja rekurencyjnego spłaszczania, która obsługuje zarówno krotki, jak i listy, i pozwala wrzucić dowolną mieszankę argumentów pozycyjnych. Zwraca generator, który produkuje całą sekwencję w kolejności, arg po arg:

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

Stosowanie:

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]

Ta wersja flattenpozwala uniknąć limitu rekurencji Pythona (a zatem działa z dowolnie głębokimi, zagnieżdżonymi iteracjami). Jest to generator, który może obsługiwać ciągi znaków i dowolne iterowalne (nawet nieskończone).

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

Oto kilka przykładów demonstrujących jego użycie:

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]

Chociaż flattenmoże obsługiwać nieskończone generatory, nie może obsługiwać nieskończonego zagnieżdżania:

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

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

Oto kolejna odpowiedź, która jest jeszcze bardziej interesująca ...

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)

Zasadniczo konwertuje zagnieżdżoną listę na ciąg, używa wyrażenia regularnego, aby usunąć zagnieżdżoną składnię, a następnie konwertuje wynik z powrotem na (spłaszczoną) listę.

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

Możesz użyć deepflattenz pakietu innej firmy 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]

Jest to iterator, więc musisz iterować (na przykład owijając go listlub używając w pętli). Wewnętrznie wykorzystuje podejście iteracyjne zamiast podejścia rekurencyjnego i jest napisane jako rozszerzenie C, dzięki czemu może być szybsze niż podejście czysto pythonowe:

>>> %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)

Jestem autorem iteration_utilitiesbiblioteki.

Zabawnie było stworzyć funkcję, która mogłaby spłaszczyć nieregularne listy w Pythonie, ale oczywiście do tego właśnie służy Python (aby programowanie było przyjemnością). Poniższy generator działa dość dobrze z pewnymi zastrzeżeniami:

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

Będzie spłaszczyć typy danych, które można chcesz pozostawione same (jak bytearray, bytesoraz strobiektów). Ponadto kod opiera się na fakcie, że żądanie iteratora od nie iterowalnego powoduje podniesienie wartości 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]
>>>

Edytować:

Nie zgadzam się z poprzednim wdrożeniem. Problem polega na tym, że nie powinieneś być w stanie spłaszczyć czegoś, co nie jest iterowalne. Jest to mylące i daje błędne wrażenie argumentu.

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

Poniższy generator jest prawie taki sam jak pierwszy, ale nie ma problemu ze spłaszczeniem obiektu, który nie jest iterowalny. Nie udaje się, jak można się spodziewać, gdy zostanie podany niewłaściwy argument.

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

Testowanie generatora działa poprawnie z dostarczoną listą. Jednak nowy kod podniesie wartość, TypeErrorgdy zostanie mu podany obiekt nieuleczalny. Przykłady pokazano poniżej nowego zachowania.

>>> 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
>>>

Chociaż wybrano elegancką i bardzo pytoniczną odpowiedź, przedstawię moje rozwiązanie tylko do recenzji:

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

Powiedz, jak dobry lub zły jest ten kod?

Wolę proste odpowiedzi. Brak generatorów. Brak limitów rekurencyjnych lub rekurencyjnych. Tylko iteracja:

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

Działa to z dwiema listami: wewnętrzną pętlą for i zewnętrzną pętlą while.

Wewnętrzna pętla for iteruje listę. Jeśli znajdzie element listy, to (1) używa list.extend () do spłaszczenia tej części pierwszego poziomu zagnieżdżenia i (2) przełącza opcję KeepChecking na True. keepchecking służy do sterowania zewnętrzną pętlą while. Jeśli zewnętrzna pętla zostanie ustawiona na wartość true, wyzwala wewnętrzną pętlę dla kolejnego przejścia.

Te przejścia odbywają się, dopóki nie zostaną znalezione zagnieżdżone listy. Kiedy w końcu nastąpi podanie, gdy nie zostanie znalezione, keepChecking nigdy nie zostanie wyzwolony na true, co oznacza, że ​​listIsNested pozostaje fałszywy, a zewnętrzna pętla while kończy działanie.

Spłaszczona lista jest następnie zwracana.

Testowe uruchomienie

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

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

Oto prosta funkcja, która spłaszcza listy o dowolnej głębokości. Brak rekurencji, aby uniknąć przepełnienia stosu.

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

Dziwię się, że nikt o tym nie pomyślał. Cholerna rekursja Nie otrzymuję rekurencyjnych odpowiedzi, które zrobili tu zaawansowani ludzie. w każdym razie tutaj jest moja próba. zastrzeżenie jest bardzo specyficzne dla przypadku użycia PO

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)

wynik:

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

Nie przejrzałem tutaj wszystkich już dostępnych odpowiedzi, ale oto jeden linijka, którą wymyśliłem, zapożyczając z pierwszego sposobu lisp i przetwarzania listy odpoczynku

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

oto jedna prosta i jedna nie taka prosta sprawa -

>>> 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]
>>> 

Próbując odpowiedzieć na takie pytanie, naprawdę musisz podać ograniczenia kodu, który zaproponujesz jako rozwiązanie. Gdyby chodziło tylko o występy, nie miałbym nic przeciwko, ale większość kodów zaproponowanych jako rozwiązanie (w tym zaakceptowana odpowiedź) nie spłaszcza żadnej listy o głębokości większej niż 1000.

Kiedy mówię większość kodów, mam na myśli wszystkie kody, które używają dowolnej formy rekurencji (lub wywołują standardową funkcję biblioteki, która jest rekurencyjna). Wszystkie te kody zawodzą, ponieważ dla każdego z wykonanych wywołań rekurencyjnych stos (wywołań) rośnie o jedną jednostkę, a stos (domyślny) wywołań python ma rozmiar 1000.

Jeśli nie znasz się zbytnio na stosie wywołań, być może poniższe informacje pomogą (w przeciwnym razie możesz po prostu przewinąć do Implementacji ).

Rozmiar stosu wywołań i programowanie rekurencyjne (analogia lochów)

Odnalezienie skarbu i wyjście

Wyobraź sobie, że wchodzisz do ogromnego lochu z ponumerowanymi pokojami i szukasz skarbu. Nie znasz tego miejsca, ale masz pewne wskazówki, jak znaleźć skarb. Każde wskazanie jest zagadką (trudność jest różna, ale nie można przewidzieć, jak trudne będą). Postanawiasz trochę pomyśleć o strategii oszczędzania czasu, robisz dwie obserwacje:

1. Trudno (długo) znaleźć skarb, ponieważ będziesz musiał rozwiązać (potencjalnie trudne) zagadki, aby się tam dostać.
2. Po znalezieniu skarbu powrót do wejścia może być łatwy, musisz po prostu podążać tą samą ścieżką w drugą stronę (choć to wymaga trochę pamięci, aby przywołać twoją ścieżkę).

Wchodząc do lochu, zauważysz mały notatnik . Postanawiasz użyć go do spisania każdego pomieszczenia, z którego wyjdziesz po rozwiązaniu zagadki (po wejściu do nowego pokoju), w ten sposób będziesz mógł wrócić z powrotem do wejścia. To genialny pomysł, nawet nie wydasz ani grosza wdrożenie swojej strategii.

Wchodzisz do lochu, rozwiązując z powodzeniem pierwsze 1001 zagadek, ale nadchodzi coś, czego nie planowałeś, nie ma już miejsca w pożyczonym notesie. Postanawiasz porzucić swoją misję, ponieważ wolisz nie mieć skarbu niż zagubić się na zawsze w lochu (to wygląda naprawdę mądrze).

Wykonywanie programu rekurencyjnego

Zasadniczo jest to dokładnie to samo, co znalezienie skarbu. Loch jest pamięcią komputera , Twoim celem nie jest teraz znalezienie skarbu, ale obliczenie jakiejś funkcji (znajdź f (x) dla danego x ). Wskazania są po prostu podprogramami, które pomogą ci rozwiązać f (x) . Twoja strategia jest taka sama jak strategia stosu wywołań , notebook to stos, pokoje to adresy zwrotne funkcji:

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))

Problem napotkany w lochu będzie tutaj taki sam, stos wywołań ma skończony rozmiar (tutaj 1000), a zatem jeśli wprowadzisz zbyt wiele funkcji bez powrotu, wypełnisz stos wywołań i pojawi się błąd, który wygląda jak „Drogi poszukiwaczu przygód, bardzo mi przykro, ale twój notatnik jest pełny” :RecursionError: maximum recursion depth exceeded . Zauważ, że nie potrzebujesz rekurencji, aby wypełnić stos wywołań, ale jest bardzo mało prawdopodobne, aby nierekurencyjny program wywoływał 1000 funkcji bez powrotu. Ważne jest również, aby zrozumieć, że po powrocie z funkcji stos wywołań jest zwalniany z użytego adresu (stąd nazwa „stos”, adres zwrotny jest wpychany przed wejściem do funkcji i wyciągany podczas powrotu). W szczególnym przypadku prostej rekurencji (funkcjafktóre wywołują się raz po raz - raz za razem - będziesz wchodził fw kółko, aż obliczenia się zakończą (aż do znalezienia skarbu) i powrócisz, fdopóki nie wrócisz do miejsca, do którego dzwoniłeś fw pierwszej kolejności. Stos wywołań nigdy nie zostanie uwolniony od niczego, dopóki nie zostanie zwolniony ze wszystkich adresów zwrotnych jeden po drugim.

Jak uniknąć tego problemu?

To właściwie dość proste: „nie używaj rekurencji, jeśli nie wiesz, jak głęboko może ona sięgać”. Nie zawsze jest to prawdą, ponieważ w niektórych przypadkach rekurencję Tail Call można zoptymalizować (TCO) . Ale w Pythonie tak nie jest, a nawet „dobrze napisana” funkcja rekurencyjna nie zoptymalizuje wykorzystania stosu. Guido ma interesujący post na ten temat: Eliminacja rekurencji ogona .

Istnieje technika, której można użyć do iteracji dowolnej funkcji rekurencyjnej, którą możemy nazwać przyniesieniem własnego notatnika . Na przykład w naszym konkretnym przypadku po prostu przeglądamy listę, wejście do pokoju jest równoznaczne z wejściem na listę podrzędną. Pytanie, które powinieneś sobie zadać, to jak mogę wrócić z listy do listy nadrzędnej? Odpowiedź nie jest tak skomplikowana, powtarzaj następujące czynności, ażstackbędzie pusta:

1. wcisnąć aktualną listę addressi indexw stackprzypadku wprowadzania nowego podmenu (Należy pamiętać, że adres lista + indeks jest również adres, dlatego wystarczy użyć dokładnie taką samą technikę stosowaną przez stos wywołań);
2. za każdym razem, gdy element zostanie znaleziony, yieldto (lub dodaj je do listy);
3. gdy lista zostanie w pełni zbadana, wróć do listy nadrzędnej za pomocą stack returnaddress (i index) .

Zauważ również, że jest to równoważne z DFS w drzewie, w którym niektóre węzły są listami podrzędnymi, A = [1, 2]a niektóre są prostymi elementami: 0, 1, 2, 3, 4(dlaL = [0, [1,2], 3, 4] ). Drzewo wygląda następująco:

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

Wstępne zamówienie przejścia DFS to: L, 0, A, 1, 2, 3, 4. Pamiętaj, że aby zaimplementować iteracyjny DFS, musisz również „mieć stos”. Wdrożenie, które zaproponowałem wcześniej, skutkuje następującymi stanami (dla stackiflat_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]

W tym przykładzie maksymalny rozmiar stosu wynosi 2, ponieważ lista wejściowa (a zatem drzewo) ma głębokość 2.

Realizacja

W przypadku implementacji w Pythonie można nieco uprościć, używając iteratorów zamiast prostych list. Odniesienia do (pod) iteratorów będą używane do przechowywania adresów zwrotnych list podrzędnych (zamiast posiadania zarówno adresu listy, jak i indeksu). Nie jest to duża różnica, ale uważam, że jest to bardziej czytelne (a także nieco szybsze):

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)

Zauważ też, że w „ is_list_likeMam” isinstance(item, list), który można zmienić w celu obsługi większej liczby typów danych wejściowych, tutaj chciałem mieć najprostszą wersję, w której (iterowalna) jest tylko listą. Ale możesz też to zrobić:

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

Traktuje to ciągi jako „proste elementy” i dlatego flatten_iter([["test", "a"], "b])wróci ["test", "a", "b"]i nie ["t", "e", "s", "t", "a", "b"]. Zauważ, że w takim przypadkuiter(item) jest wywoływany dwukrotnie na każdym elemencie, udawajmy, że jest to ćwiczenie dla czytelnika, aby uczynić to czystszym.

Testowanie i uwagi na temat innych wdrożeń

W końcu, należy pamiętać, że nie można wydrukować nieskończenie zagnieżdżonej listy Lużywając print(L)ponieważ wewnętrznie użyje do wywołań cyklicznych __repr__( RecursionError: maximum recursion depth exceeded while getting the repr of an object). Z tego samego powodu rozwiązania flattendotyczące strniepowodzenia zakończy się niepowodzeniem z tym samym komunikatem o błędzie.

Jeśli potrzebujesz przetestować swoje rozwiązanie, możesz użyć tej funkcji do wygenerowania prostej listy zagnieżdżonej:

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

Co daje: build_deep_list(5)>>> [4, [3, [2, [1, [0]]]]].

Oto compiler.ast.flattenimplementacja w 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

Są lepsze, szybsze metody (jeśli tu dotarłeś, już je widziałeś)

Uwaga:

Przestarzałe od wersji 2.6: Pakiet kompilatora został usunięty w Pythonie 3.

całkowicie hacky, ale myślę, że to zadziała (w zależności od typu data_type)

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

Wystarczy użyć funcybiblioteki: pip install funcy

import funcy


funcy.flatten([[[[1, 1], 1], 2], 3]) # returns generator
funcy.lflatten([[[[1, 1], 1], 2], 3]) # returns list

Oto inne podejście do py2, nie jestem pewien, czy jest to najszybsze, najbardziej eleganckie i najbezpieczniejsze ...

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))

Może zignorować dowolny określony (lub wyprowadzony) typ, który chcesz, zwraca iterator, dzięki czemu można go przekonwertować na dowolny konkretny kontener, taki jak lista, krotka, dykta lub po prostu zużyć w celu zmniejszenia zużycia pamięci, na lepsze lub gorsze może obsłużyć początkowe obiekty, które nie są iterowalne, takie jak int ...

Zauważ, że większość ciężkiego podnoszenia odbywa się w C, ponieważ o ile wiem, jak to jest zaimplementowane itertools, więc podczas gdy jest rekurencyjny, AFAIK nie jest ograniczony głębokością rekurencji pytona, ponieważ wywołania funkcji występują w C, chociaż to nie oznacza, że ​​jesteś ograniczony pamięcią, szczególnie w OS X, gdzie jego rozmiar stosu ma obecnie twardy limit (OS X Mavericks) ...

istnieje nieco szybsze podejście, ale mniej przenośna metoda, użyj go tylko wtedy, gdy możesz założyć, że podstawowe elementy danych wejściowych można jawnie określić inaczej, otrzymasz nieskończoną rekurencję, a OS X z ograniczonym rozmiarem stosu będzie rzucić błąd segmentacji dość szybko ...

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))

tutaj używamy zestawów do sprawdzania typu, więc potrzeba O (1) vs O (liczba typów), aby sprawdzić, czy element powinien zostać zignorowany, ale oczywiście każda wartość z typem pochodnym podanych ignorowanych typów zawiedzie , dlatego używa str,unicode więc używaj go ostrożnie ...

testy:

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

Bez użycia biblioteki:

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]

Używanie 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

Lub bez łączenia:

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)

Użyłem rekurencji do rozwiązania zagnieżdżonej listy z dowolną głębokością

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

Więc po zdefiniowaniu funkcji Combine_nlist łatwo jest użyć tej funkcji do spłaszczania. Lub możesz połączyć to w jedną funkcję. Podoba mi się moje rozwiązanie, ponieważ można je zastosować do dowolnej listy zagnieżdżonej.

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

wynik

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]

Najprostszym sposobem jest użycie biblioteki Morphpip install morph .

Kod to:

import morph

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

Wiem, że jest już wiele niesamowitych odpowiedzi, ale chciałem dodać odpowiedź, która wykorzystuje funkcjonalną metodę programowania rozwiązania problemu. W tej odpowiedzi wykorzystuję podwójną rekurencję:

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]]))

wynik:

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

Nie jestem pewien, czy to niekoniecznie jest szybsze czy bardziej skuteczne, ale właśnie to robię:

def flatten(lst):
    return eval('[' + str(lst).replace('[', '').replace(']', '') + ']')

L = [[[1, 2, 3], [4, 5]], 6]
print(flatten(L))

Ta flattenfunkcja zamienia listę w ciąg znaków, usuwa wszystkie nawiasy kwadratowe, przyczepia nawiasy kwadratowe z powrotem na końcach i zamienia z powrotem w listę.

Chociaż, gdybyś wiedział, że będziesz mieć nawiasy kwadratowe na liście, na przykład [[1, 2], "[3, 4] and [5]"], będziesz musiał zrobić coś innego.

Jest to prosta implementacja spłaszczania na 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]

Spłaszczy to listę lub słownik (lub listę list lub słowników itp.). Zakłada, że ​​wartości są łańcuchami i tworzy ciąg, który konkatenuje każdy element z argumentem separatora. Jeśli chcesz, możesz użyć separatora, aby podzielić wynik na obiekt listy. Używa rekurencji, jeśli następną wartością jest lista lub ciąg znaków. Użyj argumentu klucza, aby określić, czy chcesz, czy klucze lub wartości (ustaw klucz na false) z obiektu słownika.

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=', ')

daje:

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

Jeśli podoba Ci się rekurencja, może to być interesujące dla Ciebie rozwiązanie:

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

Zaadaptowałem to na podstawie kodu schematu ćwiczeń, który napisałem jakiś czas temu.

Cieszyć się!

Jestem nowy w Pythonie i pochodzę z seplenia. Oto, co wymyśliłem (sprawdź nazwy var dla 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]

Wydaje się, że działa. Test:

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

zwroty:

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