rekursion, alle zwischenergebnisse speichern

[blutigeranfaenger]

Hallo zusammen,
ich habe folgende Problem:
Ich möchte beim rekursiven Aufruf eines Skripts alle Zwischenergebnisse speichern.
Im konkreten Fall werden aus einem Wort alle substrings gebildet, die um 1 kürzer sind als dieses Wort.
Diese substrings werden in der Liste "interim" gespeichert.
Jedes Element von interim erzeugt nun wiederum eine neues interim, usw.
Das klappt soweit auch, ich sehe das, wenn ich interim ausdrucke.
Aber am Ende möchte ich eine liste mit sämtlichen Substrings haben und das klappt nicht.
Nur die oberste Liste interim wird am Ende gespeichert.
Wie könnte ich das ändern?
Hier mein Code:

Code: Alles auswählen

#!/usr/bin/env python3
from itertools import combinations
def substrings(nstring,l):
    allsubs = [ ]
    if l >1:
        alist = [ ]
        interim = [ ]
        for s in nstring:
            alist.append(s)
        combis = list(combinations(alist,l))
        for c in combis:
            sub =""
            for i in c:
                sub += i
            interim.append(sub)
        print(interim)
        allsubs.append(interim)
        for i in interim:
            nstring= i
        substrings(nstring,l-1)
    return allsubs
print(substrings("Lösung",5))

[darktrym]

Wenn du irgendetwas speichern willst solltest du das auch als Argument übergeben, korrekt?

[Sirius3]

Der Code ist sehr schwierig zu lesen, weil die Variablennamen entweder nur einbuchstabig sind, oder kryptische Anhängsel haben, wie bei nstring oder alist.
Benutze sprechende Namen.

Code: Alles auswählen

#!/usr/bin/env python3 
from itertools import combinations

def create_substrings(string, length):
    all_substrings = []
    if length > 1:
        substrings = [
            "".join(combination)
            for combination in combinations(string, length)
        ]
        print(substrings) 
        all_substrings.append(substrings)
        create_substrings(substrings[-1], length - 1) 
    return all_substrings

print(create_substrings("Lösung", 5))

Wenn die length immer die Länge des Strings - 1 ist, dann ist das Argument überflüssig und vereinfacht den Code zusätzlich.
Mit dem Rückgabewert des rekursiven Aufrufs machst Du nichts, warum sollte der also "gespeichert" werden?

[blutigeranfaenger]

Danke für die Antwort.
Was ich noch nicht kannte ist die Geschichte mit

Code: Alles auswählen

substrings = [
            "".join(combination)
            for combination in combinations(string, length)
        ]

Ich hätte nicht gedacht, dass man an dieser Stelle eine Einrückung machen kann.
Es stimmt, bei diesem meinem Beispielskript mache ich nichts mit dem Substrings. Bei dem was ich eigentlich will, brauche ich die Substrings aber und deshalb möchte ich sie auch speichern. Geht das und wenn ja wie? Das würde mich interessieren.

[Sirius3]

Indem Du den Rückgabewert an Deine Liste all_substrings hängst.

Die Einrückung ist nur der besseren Lesbarkeit wegen. Das Konstrukt nennt sich List-Comprehension.

[__blackjack__]

@blutigeranfaenger: Du hast in Deiner Funktion einen rekursiven Aufruf der ja auch wieder Zeichenketten erstellt und zurück gibt. Mit diesem Rückgabewert machst Du aber nichts. Wenn die übergeordnete Funktion damit was machen soll, müsste da halt Code stehen der mit dem Rückgabewert was macht.

Wobei der rekursive Aufruf an sich hier schon fragwürdig ist IMHO, denn der ersetzt im Grunde ja nur eine normale Schleife, also sollte man das auch einfach als normale Schleife schreiben. Anderseits möchtest Du vielleicht auch eine Lösung haben die tatsächlich rekursiv ist und mehr Teilzeichenketten produziert‽

Ausgehend vom Code von Sirius3 kann man *das* jedenfalls problemlos ohne Rekursion lösen:

Code: Alles auswählen

#!/usr/bin/env python3
from itertools import combinations
from pprint import pprint


def create_substrings(string, substring_length=None):
    if substring_length is None:
        substring_length = len(string) - 1

    result = []
    for length in reversed(range(2, substring_length + 1)):
        result.append(
            [
                "".join(combination)
                for combination in combinations(string, length)
            ]
        )
        string = result[-1][-1]

    return result


def main():
    pprint(create_substrings("Lösung"))


if __name__ == "__main__":
    main()

(Falls man diese Funktion eigentlich immer ohne zweites Argument aufruft, dann sollte das zweite Argument weg.)

Ausgabe:

Code: Alles auswählen

[['Lösun', 'Lösug', 'Lösng', 'Löung', 'Lsung', 'ösung'],
 ['ösun', 'ösug', 'ösng', 'öung', 'sung'],
 ['sun', 'sug', 'sng', 'ung'],
 ['un', 'ug', 'ng']]

Wobei man sich bei Verwendung von `itertools` natürlich auch überlegen kann, und vielleicht auch sollte, ob man da wirklich eine potentiell riesige Liste zurückgeben sollte, oder nicht vielleicht selbst einen Iterator von Iteratoren, oder mindestens einen Iterator von Listen. Wenn der Aufrufer das unbedingt alles auf einmal in einer Liste haben möchte, kann der das dann ja immer noch alles auf einmal im Speicher ansammeln.

Wie ist das eigentlich mit mehrfach vorkommenden Teilzeichenketten? Bei "Lösung" taucht so etwas nicht auf, aber bei "Missisippi":

Code: Alles auswählen

[['Missisipp',
  'Missisipi',
  'Missisipi',
  'Missisppi',
  'Missiippi',
  'Misssippi',
  'Misisippi',
  'Misisippi',
  'Mssisippi',
  'issisippi'],
 ['issisipp',
  'issisipi',
  'issisipi',
  'issisppi',
  'issiippi',
  'isssippi',
  'isisippi',
  'isisippi',
  'ssisippi'],
 ['ssisipp',
  'ssisipi',
  'ssisipi',
  'ssisppi',
  'ssiippi',
  'sssippi',
  'sisippi',
  'sisippi'],
 ['sisipp', 'sisipi', 'sisipi', 'sisppi', 'siippi', 'ssippi', 'isippi'],
 ['isipp', 'isipi', 'isipi', 'isppi', 'iippi', 'sippi'],
 ['sipp', 'sipi', 'sipi', 'sppi', 'ippi'],
 ['ipp', 'ipi', 'ipi', 'ppi'],
 ['pp', 'pi', 'pi']]

[blutigeranfaenger]

Sorry, aber ich stehe leider immer noch mächtig auf dem Schlauch.
Ich habe es probiert mit

Code: Alles auswählen

#!/usr/bin/env python3 
from itertools import combinations

def create_substrings(string, length):
    superlist = [ ]
    if length > 1:
        all_substrings = [ ]
        substrings = [
            "".join(combination)
            for combination in combinations(string, length)
        ]
        print(substrings) 
        all_substrings.append(substrings)
        create_substrings(substrings[-1], length - 1) 
        superlist.append(all_substrings)
    return superlist

Das Ergebnis ist leider immer noch dasselbe!

[__blackjack__]

@blutigeranfaenger: Nee, das Ergebnis ist nicht das selbe, Du bekommst das was Du vorher hattest *noch mal* in eine zusätzliche Liste verpackt. Die `superlist`. Schau Dir das ``return`` an und gehe zwei Zeilen höher: Da wird `create_substrings()` aufgerufen. Das liefert als Ergebnis eine Liste. Mit dieser Liste machst Du *nichts*. Die wird also erstellt, und einfach wieder verworfen.

Aber wie ich ja schon gezeigt habe: das was da gemacht wird, braucht überhaupt gar keine Rekursion. Das macht die Funktion nur unnötig kompliziert.

Vielleicht möchtest Du ja *wirklich* etwas rekursiv machen, dann ist dieser eine Aufruf pro (Unter)Länge aber auch zu wenig.

Ist die Länge denn eigentlich immer die Zeichenkettenlänge -1? Dann wäre auch `combinations()` unnötig kompliziert, denn das könnte man sich selbst einfacher Programmieren, denn das bedeutet einfach nur, das jedes Zeichen einmal weg gelassen wird. Da wäre `combinations()` mit Kanonen auf Spatzen geschossen.

[Sirius3]

Außer, dass Du jetzt eine weitere (überflüssige) Liste eingefügt hast, machst Du immer noch nichts mit dem Rückgabewert von create_substrings. Der liefert Ergebnislisten, die Du mit der Ergebnisliste aus dem aktuellen Durchlauf kombinieren musst.

[__blackjack__]

@blutigeranfaenger: Ich denke auch wir sollten erst einmal zwei grundsätzlichere Fragen klären bevor wir hier noch länger an einer vielleicht falschen und/oder zu komplexen Lösung basteln:

1. ist das zweite Argument tatsächlich notwendig oder ergibt sich das immer aus der Länge des ersten Arguments?

2. Ist die bisherige Lösung bis auf das sammeln in einer Liste überhaupt richtig/vollständig? Es ist beim Ausgangswort "Lösung" bei den Teilzeichenketten mit der Länge 4 ja beispielsweise nicht "Lsng" dabei. Warum nicht? Soweit ich weiss garantiert `combinations()` keine Reihenfolge der Ergebnisse, das ist also recht willkürlich welche *eine* Teilzeichenkette einer Länge als Basis für die Teilzeichenketten der nächstkleineren Länge verwendet wird. Oder anders ausgedrückt, könnte man statt ``substrings[-1]`` auch ``random.choice(substrings)`` verwenden? Denn darauf läuft es ja im Grunde hinaus, das *ein* Teilergebnis besonders behandelt wird, man aber nicht wirklich weiss welches.

Vielleicht verrätst Du auch einfach mal wofür das Ergebnis verwendet werden soll.