Python: Verwenden eines rekursiven Algorithmus als Generator

Question

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

Hier ist ein Beispiel. Angenommen, wir wollen alle Permutationen eines Strings mit einer rekursiven Funktion berechnen. Der folgende naive Algorithmus nimmt ein zusätzliches Argument ‚Lagerung‘ und fügt ihm eine Permutation, wenn es so findet man:

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 um Ineffizienz sich nicht, dies ist nur ein Beispiel)

Jetzt ich möchte, dass meine Funktion in einen Generator drehen, dh eine Permutation zu erhalten, anstatt sie auf der Speicherliste anhängt:

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 Arbeit (die Funktion verhält sich wie ein leerer Generator).

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

Answer 1

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 

Answer 2

Der Innenraum Aufruf getPermutations - es ist ein Generator, auch.

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 sich mit einer for-Schleife durch das iterieren (siehe @MizardX Posting, das mich von Sekunden verdrängte!)

Answer 3

Dies vermeidet die len(string) -deep Rekursion, und ist im Allgemeinen ein schönes Art und Weise Generatoren-inside-Generatoren zu handhaben:

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 

flatten ermöglicht es uns, indem sie einfach yield ing es, statt durch sie Laufen Fortschritte in einem anderen Generator fortzusetzen und yield jedes Element ing manuell.

---

3,3 Python wird yield from die Syntax hinzufügen, die zu einem Teilgenerator für natürliche Delegation erlaubt:

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