Python: Verwenden eines rekursiven Algorithmus als Generator

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 die Sequenzen mehrere Tausend sind. Daher würde ich meinen Algorithmus lieber 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 eines Strings mit einer rekursiven Funktion berechnen. Der folgende naive Algorithmus verwendet ein zusätzliches Argument 'Speicher' und fügt ihm eine Permutation hinzu, 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, dh eine Permutation ergeben, 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 funktioniert nicht (die Funktion verhält sich wie ein leerer Generator).

Vermisse ich etwas Gibt es eine Möglichkeit, den obigen rekursiven Algorithmus in einen Generator umzuwandeln, ohne ihn durch einen iterativen zu ersetzen ?

def getPermutations(string, prefix=""):
    if len(string) == 1:
        yield prefix + string
    else:
        for i in xrange(len(string)):
            for perm in getPermutations(string[:i] + string[i+1:], prefix+string[i]):
                yield perm

Oder ohne Akku:

def getPermutations(string):
    if len(string) == 1:
        yield string
    else:
        for i in xrange(len(string)):
            for perm in getPermutations(string[:i] + string[i+1:]):
                yield string[i] + perm

Dies vermeidet die len(string)tiefe Rekursion und ist im Allgemeinen eine gute Möglichkeit, mit Generatoren innerhalb von Generatoren umzugehen:

from types import GeneratorType

def flatten(*stack):
    stack = list(stack)
    while stack:
        try: x = stack[0].next()
        except StopIteration:
            stack.pop(0)
            continue
        if isinstance(x, GeneratorType): stack.insert(0, x)
        else: yield x

def _getPermutations(string, prefix=""):
    if len(string) == 1: yield prefix + string
    else: yield (_getPermutations(string[:i]+string[i+1:], prefix+string[i])
            for i in range(len(string)))

def getPermutations(string): return flatten(_getPermutations(string))

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

flattenermöglicht es uns, den Fortschritt in einem anderen Generator fortzusetzen, indem wir ihn einfach yieldbearbeiten, anstatt ihn zu durchlaufen und yieldjedes Element manuell zu bearbeiten.

Python 3.3 ergänzt yield fromdie Syntax, die eine natürliche Delegierung an einen Subgenerator ermöglicht:

def getPermutations(string, prefix=""):
    if len(string) == 1:
        yield prefix + string
    else:
        for i in range(len(string)):
            yield from getPermutations(string[:i]+string[i+1:], prefix+string[i])

Der innere Aufruf von getPermutations - es ist auch ein Generator.

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

Sie müssen dies mit einer for-Schleife durchlaufen (siehe @ MizardX-Posting, das mich um Sekunden verdrängt hat!)