webentwicklung-frage-antwort-db.com.de

Python: Verwenden eines rekursiven Algorithmus als Generator

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 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?

pythonrecursiongenerator
99
Federico A. Ramponi
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
117
Markus Jarderot

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

flatten ermöglicht es uns, den Fortschritt in einem anderen Generator fortzusetzen, indem wir einfach yield diesen durchlaufen, anstatt ihn zu durchlaufen und yield jedes Element manuell zu bearbeiten.

Python 3.3 wird hinzufügen yield from zur Syntax, die eine natürliche Delegation an einen Untergenerator 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])
28
ephemient

Der interne 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!)

19
S.Lott