Spłaszcz nieregularną listę list

440

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?

telliott99
źródło
16
Fakt, że jest tak wiele odpowiedzi i tyle akcji na to pytanie, naprawdę sugeruje, że powinna to być gdzieś wbudowana funkcja, prawda? Szczególnie szkoda, że ​​compiler.ast został usunięty z Python 3.0
Mittenchops
3
Powiedziałbym, że to, czego tak naprawdę potrzebuje Python, to nieprzerwana rekurencja, a nie kolejne wbudowane narzędzie.
glina
2
@Mittenchops: całkowicie się nie zgadzam, fakt, że ludzie pracujący z wyraźnie złymi interfejsami API / zbyt skomplikowanymi strukturami danych (tylko uwaga: listma być jednorodny) nie oznacza, że ​​jest to wina Pythona i potrzebujemy wbudowanego do takiego zadania
Azat Ibrakov
1
Jeśli możesz sobie pozwolić na dodanie pakietu do swojego projektu - przypuszczam, że rozwiązanie more_itertools.collapse zrobi to najlepiej. Z tej odpowiedzi: stackoverflow.com/a/40938883/3844376
viddik13

Odpowiedzi:

382

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
Cristian
źródło
6
Ze wszystkich sugestii na tej stronie jest to jedyna, która błyskawicznie spłaszczyła tę listę, l = ([[chr(i),chr(i-32)] for i in xrange(ord('a'), ord('z')+1)] + range(0,9))gdy to zrobiłem list(flatten(l)). Wszyscy inni zaczną działać i będą trwać wiecznie!
nemesisfixx
7
Spłaszcza to również słowniki. Może chcesz użyć collections.Sequencezamiast collections.Iteratable?
josch
1
To nie działa z rzeczami, które początkowo nie są listami, np for i in flatten(42): print (i). Można to naprawić, przesuwając isinstanceklauzulę -test i else-poza for elpętlę. (Wtedy mógłbyś cokolwiek na to rzucić, a to by z niego spłaszczyło listę)
RolKau
6
W Pythonie 3.7 używanie collections.Iterablejest przestarzałe. Użyj collections.abc.Iterablezamiast tego.
dawg
5
Rzeczywiście rekurencja nigdy nie jest potrzebna. W tym konkretnym przypadku użycie rekurencji nie jest najlepszym rozwiązaniem, ponieważ spowoduje awarię list głęboko zagnieżdżonych (głębokość> 1000). Ale jeśli nie dążysz do posiadania czegoś bezpiecznego, wtedy tak funkcje rekurencyjne są lepsze, ponieważ są o wiele łatwiejsze do odczytu / zapisu.
cglacet
50

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.

Josh Lee
źródło
5
Możesz to zrobić bez importowania czegokolwiek, jeśli tylko try: iter(x)przetestujesz, czy jest to iterowalne… Ale nie sądzę, że importowanie modułu stdlib jest wadą, której warto unikać.
abarnert
8
Warto zauważyć, że to rozwiązanie działa tylko wtedy, gdy wszystkie elementy są tego samego typuint
alfasin
1
Mogłoby to być bardziej zwięzłe, def flatten(x): return [a for i in x for a in flatten(i)] if isinstance(x, collections.Iterable) else [x]ale czytelność może być tutaj subiektywna.
Zero
4
nie działa to na łańcuchy, ponieważ łańcuchy również są iterowalne. Zamień warunek naif isinstance(x, collections.Iterable) and not isinstance(x, basestring)
aandis
36

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]
dansalmo
źródło
1
Dzięki, że działa dobrze w Pythonie 3. W wersji 2.x potrzebna jest poprzednia: for i in flatten(item): yield i
dansalmo
lista (spłaszczyć ([[ 'X'], 'Y'])) nie działa na 2.X wariantu
Sten
@ user1019129 zobacz mój komentarz nad twoim
dansalmo
Tak nie jest on z cyklu .. myślę, ponieważ ciąg jest również „array” -z-znaków
Sten
35

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)
Alex Martelli
źródło
jest to przejście drzewa w kolejności utworzonej przez zagnieżdżone listy. zwracane są tylko liście. Należy pamiętać, że ta implementacja zajmie oryginalną strukturę danych, na lepsze lub gorsze. Przyjemnie byłoby napisać taki, który zachowuje oryginalne drzewo, ale także nie musi kopiować wpisów listy.
Andrew Wagner
6
Myślę, że musisz przetestować ciągi znaków - np. Dodaj „a nie isinstance (l [0], basestring)” jak w rozwiązaniu Cristiana. W przeciwnym razie otrzymasz nieskończoną pętlę wokół l [0: 1] = l [0]
c-urchin
Jest to dobry przykład tworzenia generatora, ale jak wspomina c-urchin, sam algorytm zawodzi, gdy sekwencja zawiera łańcuchy.
Daniel 'Dang' Griffith
28

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]
samplebias
źródło
1
świetne rozwiązanie, jednak byłoby dużo pomocne, jeśli dodany jakiś komentarz do opisać e, a, npatrz
Kristof Pal
2
@WolfgangKuehne Starają argsdla n,intermediate (lub krótszy midlub może wolisz element) dla ai resultdla etak:flatten = lambda *args: (result for mid in args for result in (flatten(*mid) if isinstance(mid, (tuple, list)) else (mid,)))
wstrzymane do odwołania.
Jest to znacznie szybsze niż compiler.ast.flatten. Świetny, zwarty kod, działa na każdym (chyba) typie obiektu.
bcdan
Wow, to powinna być najbardziej głosowana i zaakceptowana odpowiedź ... działa jak urok!
U10-Forward
27

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
unutbu
źródło
1
jakikolwiek konsensus co do użycia ABC Iterable czy ABC Sequence?
wim
sets, dicts, deques, listiterators, generators, Uchwytów plików oraz niestandardowe zajęcia z __iter__zdefiniowane są wszystkie przypadki collections.Iterable, ale nie collections.Sequence. Rezultat spłaszczenia a dictjest nieco niepewny, ale poza tym uważam, że collections.Iterablelepszym rozwiązaniem jest domyślnie niż collections.Sequence. To zdecydowanie bardziej liberalne.
unutbu
@ wim: Jednym z problemów związanych z używaniem collections.Iterablejest to, że obejmuje to nieskończone generatory. Zmieniłem odpowiedź na tę sprawę.
unutbu
1
To nie wydaje się działać w przypadku trzeciego i czwartego przykładu. Rzuca StopIteration. Wygląda na to, że while True: first = next(remainder) można go zastąpić for first in remainder:.
Georgy
@Georgy można to naprawić za pomocą enkapsulacji ciała spłaszczonego w try-except StopIteration block.
baduker
12

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

glina
źródło
Jeśli spróbujesz uogólnić to na coś innego niż wartości int, będzie fajnie, np. [['C=64', 'APPLE ]['], ['Amiga', 'Mac', 'ST']]:) Z drugiej strony, biorąc pod uwagę listę, która zawiera samą siebie, zrobi to trochę lepiej niż inne odpowiedzi, podnosząc wyjątek zamiast tylko zapętlania, aż skończy się pamięć / rekursowanie, aż do wyczerpania stosu ...
abarnert
Pierwotny monit dotyczył spłaszczenia listy liczb całkowitych. Jeśli po prostu zmienisz rozumienie listy na d = [x dla x in c], to powinno działać dobrze dla twojej próbki.
glina
Po pierwsze, [x for x in c]jest to powolny i pełny sposób na zrobienie kopii c, więc dlaczego miałbyś to zrobić? Po drugie, twój kod oczywiście zamieni się 'APPLE ]['w 'APPLE ', ponieważ nie obsługuje cytowania, po prostu zakłada, że ​​wszelkie nawiasy są nawiasami listowymi.
abarnert
Ha! Sposób, w jaki twój komentarz został sformatowany na moim komputerze, nawet nie zdawałem sobie sprawy, że to miał być Apple II, tak jak pojawił się na starych komputerach. W każdym razie moja odpowiedź na oba pytania brzmi: to ćwiczenie - dla mnie - jest jedynie eksperymentem mającym na celu znalezienie twórczego rozwiązania spłaszczenia listy. Nie jestem pewien, czy uogólniłbym to, by spłaszczyć każdą listę.
glina
Musisz, arr_str = str(arr)a potem [int(s) for s in re.findall(r'\d+', arr_str)]naprawdę. Zobacz 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
źródło
8

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.

MSeifert
źródło
7

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
>>>
Noctis Skytower
źródło
5

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?

Xolve
źródło
1
Zastosowanie isinstance(i, (tuple, list)). Inicjowanie pustych zmiennych jest dla mnie flagą do szukania alternatywnych struktur kodu, zwykle pojęć, generatorów, rekurencji itp.
dansalmo
3
return type(l)(ret)otrzymamy z powrotem ten sam typ kontenera, który został przekazany. :)
dash-tom-bang
@ dash-tom-bang Czy możesz szczegółowo wyjaśnić, co to znaczy?
Xolve,
1
Jeśli prześlesz listę, prawdopodobnie chcesz ją z powrotem. Jeśli podasz krotkę, prawdopodobnie chcesz krotkę z powrotem. Jeśli zdasz miszmasz z tych dwóch, dostaniesz cokolwiek, co było otoczeniem zewnętrznym.
dash-tom-bang
4

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]

glina
źródło
Lubię też proste. W tym przypadku jednak iterujesz listę tyle razy, ile jest zagnieżdżeń lub poziomów. Może stać się drogi.
telliott99
@ telliott99: Masz rację, jeśli twoje listy są naprawdę duże i / lub zagnieżdżone na dużych głębokościach. Jeśli jednak tak nie jest, to prostsze rozwiązanie działa równie dobrze i bez głębokiej magii niektórych innych odpowiedzi. Jest miejsce na wielostopniowe rekurencyjne zrozumienie generatora, ale nie jestem przekonany, że właśnie tam powinieneś szukać. (Myślę, że wiesz, gdzie popadłem w debatę „Gorzej jest lepiej”.)
glina
@ telliott99: Innymi słowy, nie będziesz musiał „próbować Grok” mojego rozwiązania. Jeśli wydajność nie jest wąskim gardłem, co jest dla Ciebie najważniejsze jako programisty?
glina
Prostsze rozwiązania mają mniej logiki. Rekurencja jest dość podstawowym konstruktorem programowania, z którym każdy, kto uważa się za programistę, powinien czuć się całkowicie komfortowo. Generatory są bardzo podobne do Pythona i (wraz ze zrozumieniem) są czymś, co każdy profesjonalny programista w Pythonie powinien natychmiast wywołać.
dash-tom-bang
1
Zgadzam się w sprawie rekurencji. Kiedy napisałem swoją odpowiedź, python wciąż przerywał rekurencję po 1000 cyklach. Czy to zmienili? Jeśli chodzi o bycie profesjonalnym programistą python, nie jestem. Co więcej, wyobrażam sobie, że wiele osób programujących w Pythonie nie robi tego na pełny etat.
glina
4

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
Wilfred Hughes
źródło
Tak! Bardzo podobny do mojego kodu na github.com/jorgeorpinel/flatten_nested_lists/blob/master/…
Jorge Orpinel
3

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]
Syjon
źródło
3

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]
>>> 
Shreyas
źródło
To nie jest jedna wkładka. Niezależnie od tego, jak bardzo próbujesz to dopasować, def foo():jest to osobna linia. Jest to również bardzo nieczytelne.
cs95
Usunąłem kod z jednej linii i dokonałem dalszego refaktoryzacji. (edycja jest w trakcie recenzji, gdy to piszę) Ta konkretna metoda wydawała mi się bardzo czytelna, chociaż oryginalny kod wymagał pewnego refaktoryzacji.
Emilio M Bumachar,
3

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

cglacet
źródło
2

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.

pradyunsg
źródło
2

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)))
Joran Beasley
źródło
2

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
ADR
źródło
1
Do Twojej wiadomości: używa rozwiązania rekurencyjnego: link do źródła
Georgy
1

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
Samy Vilar
źródło
1

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]
alfasin
źródło
1

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)
Saksham Varma
źródło
1

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]
Młody stary
źródło
„zagnieżdżona lista o dowolnej głębokości” nieprawda. Po prostu spróbuj, a zobaczysz: current_value = combiner(current_value,each_item) RecursionError: maximum recursion depth exceeded
cglacet
hmmm, próbujesz spłaszczyć listę ponad 1000 warstw?
Oldyoung
Oczywiście o to właśnie chodzi w dyskusji na temat rozwiązań rekurencyjnych vs. iteracyjnych. Jeśli wiesz z góry, że liczba warstw jest mniejsza niż 1000, zadziała najprostsze rozwiązanie. Kiedy mówisz „dowolna głębokość”, obejmuje to listę o głębokości> 1000.
cglacet
1

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]
YPCrumble
źródło
1

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]
Leo Wahyd
źródło
1

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.

diligar
źródło
Nie ma to żadnej przewagi nad prostym rozwiązaniem, ponieważ nie przetwarza głębokich list, tj. „RecursionError: przekroczona maksymalna głębokość rekurencji podczas pobierania repr obiektu”.
cglacet
1

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]
Statham
źródło
1

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
Matt Farguson
źródło
0

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

inspectorG4dget
źródło
0

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]
Michael Puckett
źródło