Kürzlich habe ich eine Funktion geschrieben, um bestimmte Sequenzen mit nichttrivialen Einschränkungen zu generieren. Das Problem kam mit einer natürlichen rekursiven Lösung. Nun kommt es vor, dass die Sequenzen selbst bei relativ kleinen Eingaben mehrere Tausend betragen. Daher würde ich meinen Algorithmus lieber als Generator verwenden, anstatt eine Liste mit allen Sequenzen zu füllen.

Hier ist ein Beispiel. Angenommen, wir möchten alle Permutationen eines Strings mit einer rekursiven Funktion berechnen. Der folgende naive Algorithmus verwendet ein zusätzliches Argument 'storage' und hängt eine Permutation an, wenn 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, dies ist nur ein Beispiel.)

Jetzt möchte ich meine Funktion in einen Generator verwandeln, d. H. 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])

for permutation in getPermutations("abcd"):
   print permutation

Dieser Code funktioniertnicht Arbeit (die Funktion verhält sich wie ein leerer Generator).

Vermisse ich etwas? Gibt es eine Möglichkeit, den oben genannten rekursiven Algorithmus in einen Generator umzuwandelnohne es durch ein iteratives zu ersetzen?