Listen "flatten", aber mit Tiefenlimit...

[akis.kapo]

Hi all,

ich bin auf verschiedene Threads auf stackoverflow gestoßen, wie man Listen "flattened".
Naja, um ehrlich zu sein habe ich einige gute Sachen gefunden, wie z.Bsp [item for sublist in list for item in sublist]...

Aber eigentlich wollte ich was ganz was anderes: selber bestimmen, bis zu welcher "Tiefe" geflattet wird.

Sorry for mein Denglisch.

Also hab ich mich rangesetzt und bisher eine Möglichkeit gefunden, wie ich Listen mit beliebiger Tiefe rekursiv "flatt'ne":

Code: Alles auswählen

def flatten(l):
    try:
        for i in l:
            try:
                for j in flatten(i):
                    yield j
            except TypeError:
                yield i
    except TypeError:
        yield l

Dies nimmt eine Liste mit beliebig vielen Listen als Element und gibt nur die nicht-iterable Elemente zurück, und zwar in der ursprünglichen Reihenfolge.
(Hatte zwischendurch auch Versionen, die denselben Job ohne Einhaltung der Reihenfolge machen...)

Zur Veranschaulichung:

Code: Alles auswählen

>>> l
[[0, 1], [3, 4, [5, 6]], [7, 8, [9, 10, [11, 12, [13, 14]]]]]
>>> list(flatten(l))
[0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

Soweit, so gut.

Jetzt bin ich aber ein bischen über mein Ziel hinausgeschoßen.

Eigentlich will ich flatten(l, limit=N) haben, wobei limit=0 unendlich rekursiv geht, wie flatten(l).
Und limit > 0, z.Bsp. limit=1 geht nur auf eine Ebene runter:

limit=1

Code: Alles auswählen

>>> l
[[0, 1], [3, 4, [5, 6]], [7, 8, [9, 10, [11, 12, [13, 14]]]]]
>>> list(flatten(l, limit=1))
[0, 1, 3, 4, [5, 6], 7, 8, [9, 10, [11, 12, [13, 14]]]]

limit=2

Code: Alles auswählen

>>> l
[[0, 1], [3, 4, [5, 6]], [7, 8, [9, 10, [11, 12, [13, 14]]]]]
>>> list(flatten(l, limit=2))
[0, 1, 3, 4, 5, 6, 7, 8, 9, 10, [11, 12, [13, 14]]]

limit=3

Code: Alles auswählen

>>> l
[[0, 1], [3, 4, [5, 6]], [7, 8, [9, 10, [11, 12, [13, 14]]]]]
>>> list(flatten(l, limit=3))
[0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, [13, 14]]

limit=4

Code: Alles auswählen

>>> l
[[0, 1], [3, 4, [5, 6]], [7, 8, [9, 10, [11, 12, [13, 14]]]]]
>>> list(flatten(l, limit=4))
[0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

Problem ist, ich komm einfach nicht drauf, wie man das machen könnte.

Interessiert sich jemand für dieses Problem? Wenn ja, bitte ich um Hilfe.

Ich fände so eine flatten(list, limit=N) Funktion sowas von nützlich... sollte eigentlich ein PEP für ein builtin werden, findet ihr nicht?

Vielen Dank wie immer im Voraus.

[SOLVED]
EDIT: Das ging schneller als gedacht, hier die Lösung mit Dank an EyDu:

Code: Alles auswählen

def flatten(l, limit=0):
    assert limit >= 0 or limit is None
    
    if limit == 0 or limit is None:
        for e in l:
            yield e
    else:
        for e in l:
            if not isinstance(e, list):
                yield e
            else:
                if not isinstance(e, basestring):
                    for x in flatten(e, None if limit is None else limit-1):
                        yield x
                else:
                    yield e

Beispiel:

Code: Alles auswählen

>>> l = [[0, 1], [3, 4, [5, 6]], [7, 8, [9, 10, [11, 12, [13, 14]]]]]
>>> list(flatten(l))
[0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
>>> list(flatten(l, limit=1))
[0, 1, 3, 4, [5, 6], 7, 8, [9, 10, [11, 12, [13, 14]]]]
>>> list(flatten(l, limit=2))
[0, 1, 3, 4, 5, 6, 7, 8, 9, 10, [11, 12, [13, 14]]]
>>> list(flatten(l, limit=3))
[0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, [13, 14]]
>>> list(flatten(l, limit=4))
[0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
>>> list(flatten(l, limit=5))
[0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
>>> l = [[0, 1], [3, 'Hallo Welt!', [5, 6]], [7, 8, [9, 10, [11, 12, [13, 14]]]]]
>>> list(flatten(l, limit=5))
[0, 1, 3, 'Hallo Welt!', 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

[EyDu]

Hallo.

Du hast die Lösung doch eigentlich schon, es fehlen nur noch die Bedingungen. Außerdem solltest du nicht mit Werten für "unendlich entfalten" Werten. Das ist ein wenig unerwartet und in deinem Fall fällt die Null sogar noch in einen möglichen Vernünftigen ("gar nicht entfalten") Bereich. Ich habe einfach mal None verwendet, ein Prädikat wäre natürlich noch schöner.

Code: Alles auswählen

def flatten(l, limit=1):
    assert limit is None or limit >= 0
    
    if limit == 0:
        for element in l:
            yield element
    else:
        for element in l:
            if not isinstance(element, list):
                yield element
            else:
                for x in flatten(element, None if limit is None else limit-1):
                    yield x

Bei dem Test auf Iterierbarkeit musst du übrigens vorsichtig sein, denn bei Strings kann es sehr ungemütlich werden Ich habe jetzt einfach mal nur gegen Listen getestet und andere Fälle ignoriert. Je nach Anwendungsfall musst du dir selber überlegen, wass du unterstützen willst.

Edit: mit ``yield from`` bekommt man das natürlich noch kürzer hin.

[akis.kapo]

yield from???

PS: Und guter Einwand wegen Strings... ich würde aber alles zulassen, was interable ist, ausser Strings. if not isinstance(l, basestring), ...

EDIT: Habs! [SOLVED], siehe:

Code: Alles auswählen

>>> from flatten import *
>>> l = [[0, 1], [3, 4, [5, 6]], [7, 8, [9, 10, [11, 12, [13, 14]]]]]
>>> list(flatten(l))
[0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
>>> list(flatten_limit(l, limit=1))
[0, 1, 3, 4, [5, 6], 7, 8, [9, 10, [11, 12, [13, 14]]]]
>>> list(flatten_limit(l, limit=2))
[0, 1, 3, 4, 5, 6, 7, 8, 9, 10, [11, 12, [13, 14]]]
>>> list(flatten_limit(l, limit=3))
[0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, [13, 14]]
>>> list(flatten_limit(l, limit=4))
[0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
>>> list(flatten_limit(l, limit=5))
[0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
>>> l = [[0, 1], [3, 'Hallo Welt!', [5, 6]], [7, 8, [9, 10, [11, 12, [13, 14]]]]]
>>> list(flatten_limit(l, limit=5))
[0, 1, 3, 'Hallo Welt!', 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

EDIT2: Jetzt ist halt die Frage ob's nicht noch ein bischen kürzer/schöner/more pythonic geht...

[Sirius3]

@akis.kapo: die zwei Ebenen tiefe if-Verschachtelung solltest Du durch ein elif ersetzen, wobei das zweite if bei Dir im Moment immer »True« liefert.

[EyDu]

Und was hat der Test auf None im ersten if zu Suchen?

Edit: Und der Test auf None, nachdem man bereits auf >= geprüft hat ist natürlich mutig. Allerdings frage ich mich hier ernsthaft, warum Python hier keine Ausnahme wirft. Unter 3.3 gibt es eine korrekte Exception.

[snafu]

Edit: Und der Test auf None, nachdem man bereits auf >= geprüft hat ist natürlich mutig. Allerdings frage ich mich hier ernsthaft, warum Python hier keine Ausnahme wirft. Unter 3.3 gibt es eine korrekte Exception.

Weil sich in Python 2.x verschiedene Typen nach Lust und Laune vergleichen lassen, auch wenn es keinen Sinn ergibt.

[EyDu]

Stimmt. Nach ein wenig Wühlen in der Referenz konnte ich mich sogar daran erinnern, dass ich es mal vor Jahren gelesen hatte. Bei CPython scheint am Ende alles auf den Speicheradressen zu enden. Das hat natürlich auch (von mir hervorgehoben) interessante Folgen:

Most other objects of built-in types compare unequal unless they are the same object; the choice whether one object is considered smaller or larger than another one is made arbitrarily but consistently within one execution of a program.

[snafu]

EDIT2: Jetzt ist halt die Frage ob's nicht noch ein bischen kürzer/schöner/more pythonic geht...

Vielleicht so?

Code: Alles auswählen

def flatten(l, depth=1):
    result = l
    for _ in xrange(depth):
        new_result = []
        for part in result:
            try:
                new_result.extend(part)
            except TypeError:
                new_result.append(part)
        result = new_result
    return result

Der Code ist nicht perfekt, weil er nicht merkt, wann er frühzeitig aufhören kann. Dies lässt sich aber bei Bedarf natürlich noch einbauen...

EDIT: Achso, ich habe nicht beachtet, dass Strings nicht weiter zerlegt werden sollen.

[snafu]

Neue Version:

Code: Alles auswählen

def flatten(l, depth=1, allowed_iterables=(list, tuple, dict, set)):
    result = l
    for _ in xrange(depth):
        new_result = []
        for part in result:
            if isinstance(part, allowed_iterables):
                new_result.extend(part)
            else:
                new_result.append(part)
        result = new_result
    return result

[EyDu]

Code: Alles auswählen

def flatten(l, limit=0):
    assert limit >= 0 or limit is None
    
    stack = [(x, limit) for x in l[::-1]]
    
    while stack:
        data, limit = stack.pop()
        
        if not isinstance(data, list) or limit == 0:
            yield data
        else:
            for element in data[::-1]:
                stack.append((element, None if limit is None else limit-1))

[jerch]

Andere Stackvariante (ungetestet):

Code: Alles auswählen

from collections import deque

def flatten_stacked(it, limit=None):
    depth = limit or 0
    stack = deque()
    stack.appendleft((depth, it))
    while stack:
        depth, it = stack.popleft()
        if limit and depth < 0:
            yield it
            continue
        it_p = iter(it)
        for el in it_p:
            # change this to needed iterator types
            if not hasattr(el, '__iter__'):
                yield el
            else:
                stack.appendleft((depth, it_p))
                stack.appendleft((depth-1, el))
                break