Kürzlich habe ich eine Funktion geschrieben, um bestimmte Sequenzen mit nicht trivialen Einschränkungen zu generieren. Das Problem kam mit einer natürlichen rekursiven Lösung. Nun kommt es vor, dass selbst bei relativ kleinen Eingaben mehrere Tausend Sequenzen vorhanden sind, daher würde ich lieber meinen Algorithmus als Generator verwenden, anstatt ihn zum Füllen einer Liste mit allen Sequenzen zu verwenden.
Hier ist ein Beispiel. Angenommen, wir möchten alle Permutationen einer Zeichenfolge mit einer rekursiven Funktion berechnen. Der folgende naive Algorithmus nimmt ein zusätzliches Argument "storage" und hängt eine Permutation daran an, wann immer er eine findet:
def getPermutations(string, storage, prefix=""): if len(string) == 1: storage.append(prefix + string) # <----- else: for i in range(len(string)): getPermutations(string[:i]+string[i+1:], storage , prefix+string[i]) storage = [] getPermutations("abcd", storage) for permutation in storage: print permutation (Bitte kümmern Sie sich nicht um Ineffizienz, das ist nur ein Beispiel.)
Nun möchte ich meine Funktion in einen Generator verwandeln, dh eine Permutation liefern, anstatt sie an die Speicherliste anzuhängen:
def getPermutations(string , prefix=""): if len(string) == 1: yield prefix + string # <----- else: for i in range(len(string)): getPermutations(string[:i]+string [i+1:], prefix+string[i]) für Permutation in getPermutations("abcd"): print permutation Dieser Code funktioniert nicht ( die Funktion verhält sich wie ein em pty Generator).
Verpasse ich etwas? Gibt es eine Möglichkeit, den obigen rekursiven Algorithmus in einen Generator umzuwandeln, ohne ihn durch einen iterativen zu ersetzen?