Glätten eines unregelmäßigen Liste von Listen

Meine Lösung:

import collections


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

Ein wenig kürzer, aber so ziemlich das gleiche.

InformationsquelleAutor Josh Lee

Generator mit Rekursion und duck typing (aktualisiert für 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]

InformationsquelleAutor dansalmo

Hier meine funktionsfähige version von rekursiven glätten Sie die beiden Griffe Tupel und Listen, und Sie können Sie werfen in einer Mischung von positions-Argumente. Gibt ein generator erzeugt die gesamte Sequenz um, arg von arg:

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

Verwendung:

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]

InformationsquelleAutor samplebias

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

InformationsquelleAutor kev

War es Spaß zu versuchen, um eine Funktion erstellen, die könnte reduzieren unregelmäßigen Liste in Python, aber natürlich ist das, was Python ist für die (um-Programmierung Spaß). Der folgende generator funktioniert Recht gut mit einigen vorbehalten:

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

Wird es glätten Datentypen, die Sie wollen allein gelassen (wie bytearray, bytes, und str Objekte). Auch der code basiert auf der Tatsache, dass der anfragende ein iterator von einem nicht-wiederholenden wirft eine 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]
>>>

Edit:

Stimme ich mit der vorherigen Implementierung. Das problem ist, dass Sie nicht in der Lage sein zu glätten, etwas, das ist nicht durchsuchbar. Es ist verwirrend und gibt den falschen Eindruck, von das argument.

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

Den folgenden generator ist fast die gleiche wie die erste, aber nicht das problem, zu versuchen zu glätten, eine nicht-wiederholenden Objekt. Es scheitert, wie man erwarten würde, wenn ein unangebrachtes argument ist ihm gegeben.

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

Testen der generator arbeitet gut mit der Liste, der geliefert wurde. Aber der neue code wird zu erhöhen eine TypeError wenn ein nicht-wiederholenden Objekt ist gegeben. Beispiel sind unten gezeigt an das neue Verhalten.

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

InformationsquelleAutor Noctis Skytower

Bevorzuge ich einfache Antworten. Keine Generatoren. Keine Rekursion oder Rekursion Grenzen. Nur iteration:

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

Diese arbeitet mit zwei Listen: eine innere Schleife und eine äußere while-Schleife.

Die innere for-Schleife durchläuft die Liste. Wenn es feststellt, dass ein element in der Liste (1) Liste verwendet.verlängern() zu glätten, die Teil einer Schachtelung und (2) schaltet keepChecking zu Wahren. keepchecking wird verwendet, um die Kontrolle der äußeren while-Schleife. Wenn die äußere Schleife wird auf true gesetzt, löst die innere Schleife für einen weiteren Durchlauf.

Derjenigen Pässe behalten geschieht, bis keine weitere verschachtelte Listen zu finden sind. Wenn ein Durchgang schließlich Auftritt, wo keine zu finden sind, keepChecking wird nie ausgelöst true, was bedeutet listIsNested bleibt falsch und die äußere while-Schleife beendet.

Die vereinfachte Liste wird dann zurückgegeben.

Testlauf

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

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

InformationsquelleAutor clay

Hier ist die compiler.ast.flatten Umsetzung in 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

Gibt es bessere, schnellere Methoden (Wenn Sie bisher hier erreicht haben, haben Sie gesehen, wie Sie bereits)

Beachten Sie auch:

Veraltet seit version 2.6: Die compiler-Paket entfernt wurde in Python 3.

InformationsquelleAutor pradyunsg

Ich nicht gehen durch all die bereits vorhandenen Antworten hier, aber hier ist ein one-liner, die ich kam mit, in Anlehnung an lisp ist übrigens der erste-und der rest der Liste Verarbeitung

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

hier ist ein einfaches und ein nicht-so-einfachen Fall -

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

InformationsquelleAutor Shreyas

Hier ist ein weiterer py2 Ansatz, ich bin nicht sicher, ob die Schnellste oder die eleganteste, noch die sicherste ...

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

Kann es ignorieren, die spezifische (oder abgeleitet) Typ, den Sie möchten, es gibt einen iterator, so können Sie wandeln es zu jedem bestimmten container wie list, tuple, dict oder einfach verbrauchen, um weniger Speicherbedarf, für besser oder schlechter damit umgehen können ersten nicht-wiederholenden Objekte wie int ...

Hinweis: die meisten der schweren lifting erfolgt in C, da, soweit ich weiß, das ist, wie itertools umgesetzt werden, so, wenn Sie rekursiv ist, AFAIK, es ist nicht begrenzt durch python Rekursionstiefe, da die Funktionsaufrufe geschehen in C, aber dies bedeutet nicht, Sie sind begrenzt durch den Speicher, speziell in OS X, wo Ihr stack-Größe hat eine Feste Grenze, ab heute (OS X Mavericks) ...

es ist eine etwas schnellere Ansatz, aber weniger portable Methode nur verwenden, wenn Sie davon ausgehen können, dass die Basis-Elemente der Eingabe werden kann, ausdrücklich etwas anderes bestimmt ist, erhalten Sie eine Endlosschleife, und OS X mit seinen begrenzten stack-Größe, werfen Sie einen segmentation fault ziemlich schnell ...

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

hier sind wir mit Sätzen zu überprüfen, die für die Art so dauert es O(1) vs O(Anzahl von Arten), um zu prüfen, ob nicht ein element sollte ignoriert werden, obwohl natürlich jeder beliebige Wert mit abgeleiteten Typ der angegebenen ignoriert Arten wird scheitern, deshalb ist seine Verwendung str, unicode so verwenden Sie es mit Vorsicht ...

tests:

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

InformationsquelleAutor Samy Vilar

Ich verwendet rekursiv zu lösen verschachtelte Liste mit beliebiger Tiefe

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

So, nachdem ich die Funktion definieren combine_nlist, es ist einfach, um diese Funktion zu nutzen tun Planschleifen. Oder kombinieren Sie es in einer Funktion. Ich mag meine Lösung, weil es kann angewendet werden auf jede verschachtelte Liste.

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

Ergebnis

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]

InformationsquelleAutor Oldyoung

Ich bin mir bewusst dass es schon viele geniale Antworten, aber ich wollte eine Antwort, die verwendet die funktionale Programmierung-Methode der Lösung der Frage. In dieser Antwort, die ich machen Verwendung von Doppel-Rekursion :

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

Ausgabe:

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

InformationsquelleAutor Leo wahyd

Beim Versuch, solche Fragen zu beantworten, die Sie wirklich brauchen, um die Einschränkungen des Codes, den Sie vorschlagen, eine Lösung. Wenn es nur über die Leistungen, die ich würde nicht dagegen zu viel, aber die meisten der codes vorgeschlagen, als Lösung (einschließlich die akzeptierte Antwort) nicht zu glätten jede Liste hat eine Tiefe, die größer als 1000.

Wenn ich sage die meisten der codes ich meine alle codes, die jede form der Rekursion (oder rufen Sie eine standard-Bibliothek-Funktion, die rekursiv). Alle diese codes scheitern, weil für jeden rekursiven Aufruf, der (anrufen), stack wachsen, die durch eine Einheit, und die (Standard -) python-Aufrufliste hat eine Größe von 1000.

Wenn Sie nicht allzu vertraut mit den call-stack, dann vielleicht Folgendes helfen (sonst kann man nur einen Bildlauf zu der Umsetzung).

Call-stack-Größe und rekursive Programmierung (dungeon Analogie)

Finden Sie den Schatz und beenden

Stellen Sie sich vor Sie betreten ein riesiges dungeon mit nummerierten Zimmern, auf der Suche nach einem Schatz. Sie kennen nicht den Ort, aber Sie haben einige Indikationen auf, wie um den Schatz zu finden. Jede Indikation ist ein Rätsel (Schwierigkeitsgrad variiert, aber Sie können nicht Vorhersagen, wie hart Sie sein werden). Sie entscheiden, zu denken, ein wenig über eine Strategie, um Zeit zu sparen, Sie machen zwei Beobachtungen:

1. Es ist schwer (lange), den Schatz zu finden, wie werden Sie zu lösen haben (möglicherweise schwer) Rätsel, um dorthin zu gelangen.
2. Sobald der Schatz gefunden, wieder an der Einfahrt kann leicht sein, Sie müssen nur den gleichen Pfad in die andere Richtung (obwohl das muss etwas zu erinnern, Ihren Weg).

Beim betreten des Dungeons, Sie feststellen, eine kleine notebook hier. Sie entscheiden, es zu benutzen, um aufzuschreiben, jeden Raum, den Sie verlassen nach der Lösung eines Rätsels (beim betreten eines neuen Raums), auf diese Weise werden Sie in der Lage, um wieder zurück zum Eingang. Das ist eine geniale Idee, Sie nicht einmal einen cent ausgeben Umsetzung Ihrer Strategie.

Geben Sie den dungeon, die Lösung mit großem Erfolg die ersten 1001 Rätsel, aber hier kommt etwas, Sie hatte nicht geplant, Sie haben keinen Platz mehr im notebook, die Sie sich geliehen haben. Sie entscheiden aufgeben Ihrer Suche, wie Sie es vorziehen, nicht dass der Schatz als verloren, für immer im inneren des dungeon (das sieht smart in der Tat).

Ausführung eines rekursiven Programms

Im Grunde ist es genau das gleiche wie der Suche nach dem Schatz. Der Kerker ist die Arbeitsspeicher des Computers, Ihr Ziel ist jetzt nicht, den Schatz zu finden, sondern berechnen eine Funktion (finden f(x) für einen bestimmten x). Die Indikationen sind einfach sub-Routinen, die Ihnen helfen die Lösung f(x). Ihre Strategie ist die gleiche wie die call-stack Strategie, das notebook ist auf dem stack, die Zimmer sind die Funktionen der' Rückkehr-Adressen:

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

Das problem, das Sie auftreten in der dungeon wird hier gleich der Aufruf-stack hat eine endliche Größe (hier 1000) und daher, wenn Sie zu viele Funktionen ohne Rückgabe zurück dann füllst du den call-stack und Fehler, die Aussehen wie "sehr Geehrte Abenteurer, ich bin sehr Leid, aber Ihr notebook ist voll": RecursionError: maximum recursion depth exceeded. Beachten Sie, dass Sie nicht brauchen, Rekursion zu füllen, den call-stack, aber es ist sehr unwahrscheinlich, dass eine nicht-rekursive Aufruf 1000 Funktionen, ohne jemals wieder zurückkehren. Es ist wichtig zu verstehen, auch, dass, sobald Sie von einer Funktion zurückzugeben, wird der call-stack ist befreit von der Adresse verwendet (daher auch der name "Stapel", die Adresse zurück geschoben werden, bevor die Eingabe einer Funktion und holte bei der Rückkehr). Im speziellen Fall einer einfachen Rekursion (eine Funktion, die f rufen, sich einmal-über-und über -) geben Sie f über und über, bis die Berechnung beendet ist (bis der Schatz gefunden wird) - und Rückreise f bis Sie zurück zu der Stelle, wo Sie genannt f in den ersten Platz. Der call-stack wird nie befreit werden von allem, bis zum Ende, wo Sie befreit sich aus alle return-Adressen eine nach der anderen.

, Wie man dieses Problem vermeiden?

Dass ist eigentlich ziemlich einfach: "don' T verwenden Sie Rekursion, wenn Sie nicht wissen, wie tief es gehen kann". Das ist nicht immer wahr, wie in einigen Fällen, Tail Call recursion Optimiert werden können (TCO -). Aber in python ist dies nicht der Fall, und auch "gut geschrieben" rekursive Funktion nicht optimieren stack verwenden. Es ist ein interessanter Beitrag von Guido über diese Frage: Tail Recursion Elimination.

Es ist eine Technik, die Sie verwenden können, um jede rekursive Funktion iterativ, diese Technik wir nennen konnte bringen Sie Ihr eigenes notebook. Zum Beispiel, in unserem speziellen Fall, wir sind einfach erkunden, eine Liste, einen Raum betreten, ist äquivalent zu der Eingabe eine Unterliste, die Frage, die Sie sich stellen sollten, ist wie kann ich aus einer Liste zu Ihrer übergeordneten Liste? Die Antwort ist nicht so Komplex sind, wiederholen Sie die folgenden, bis die stack leer ist:

1. schieben Sie die aktuelle Liste address und index im stack bei der Eingabe einer neuen Unterliste (beachten Sie, dass eine Liste mit Adresse+index ist auch eine Adresse, also wir benutzen Sie einfach den exakt gleichen Technik, die verwendet wird, durch den Aufruf-stack);
2. jedes mal, wenn ein Element gefunden wird, wird yield es (oder fügen Sie Sie in eine Liste);
3. einmal in der Liste ist vollständig erforscht, gehen Sie zurück zu der übergeordneten Liste mit den stack zurück address (und index).

Beachten Sie auch, dass dies äquivalent zu einem DFS-Baum, wo einige Knoten sind Teillisten A = [1, 2] und einige einfache Elemente: 0, 1, 2, 3, 4 (für L = [0, [1,2], 3, 4]). Der Baum sieht wie folgt aus:

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

Den DFS-Traversierung pre-order: L, 0, A, 1, 2, 3, 4. Denken Sie daran, um eine iterative DFS Sie auch "brauchen" einen Stapel. Die Umsetzung schlug ich vor Ergebnis, mit den folgenden Staaten (für die stack und die flat_list):

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

In diesem Beispiel die maximale stack-Größe ist 2, weil die input-Liste (und somit auch der Baum) haben Tiefe 2.

Umsetzung

Für die Umsetzung in python können Sie vereinfachen ein wenig durch die Verwendung von Iteratoren anstelle von einfachen Listen. Verweise auf die (sub -) Iteratoren werden verwendet, um zu speichern Teillisten zurückgeben Adressen (anstatt der Listen-Adresse und den index). Das ist kein großer Unterschied, aber ich glaube, das ist besser lesbar (und auch ein bisschen schneller):

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)

Beachten Sie auch, dass in is_list_like ich habe isinstance(item, list), was könnte geändert werden, um zu handhaben, input-Typen, hier wollte ich nur die einfachste version, wo (durchsuchbar) ist nur eine Liste. Aber das könnte man auch machen:

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

Diese Auffassung, strings als "einfache Elemente" und daher flatten_iter([["test", "a"], "b]) zurück ["test", "a", "b"] und nicht ["t", "e", "s", "t", "a", "b"]. Bemerkung, dass in diesem Fall iter(item) genannt wird, zweimal auf jedes Element, lasst uns so tun, es ist eine übung für den Leser dieser Reiniger.

Prüfung und Bemerkungen, die auf anderen Implementierungen

Am Ende, denken Sie daran, dass Sie nicht drucken kann ein unendlich verschachtelte Liste L mit print(L) weil es intern verwenden rekursive Aufrufe __repr__ (RecursionError: maximum recursion depth exceeded while getting the repr of an object). Aus dem gleichen Grund, Lösungen flatten mit str fehl mit der gleichen Fehlermeldung.

Wenn Sie brauchen, um zu testen Ihrer Lösung können Sie diese Funktion verwenden, um zu generieren, eine einfache verschachtelte Liste:

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

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

InformationsquelleAutor cglacet

Einfach ein funcy Bibliothek:
pip install funcy

import funcy


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

InformationsquelleAutor ADR

Ich bin neu in python und kommen aus einem lisp-hintergrund. Dies ist, was ich kam mit (check-out die var-Namen für 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]

Scheint zu funktionieren. Test:

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

gibt:

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

InformationsquelleAutor Michael Puckett

Ohne Bibliothek:

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]

InformationsquelleAutor alfasin