Python: Verwenden eines rekursiven Algorithmus als Generator

Kürzlich schrieb ich eine Funktion zu generieren, die bestimmte Sequenzen mit nicht-triviale Einschränkungen. Das problem kam mit einem natürlichen rekursive Lösung. Jetzt ist es passiert, dass selbst für relativ kleine Eingang, die Sequenzen sind mehrere Tausende, so würde ich es vorziehen zu verwenden, meinen Algorithmus als generator, anstatt es zu füllen eine Liste mit allen Sequenzen.

Hier ist ein Beispiel. Nehmen wir an, wir wollen berechnen alle Permutationen eines Strings mit einer rekursiven Funktion. Der folgende naive Algorithmus nimmt ein zusätzliches argument 'storage' und fügt eine permutation auf, 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

(Please don ' T care über Ineffizienz, dies ist nur ein Beispiel.)

Nun ich möchte meine Funktion in einen generator, d.h. Sie liefern eine permutation statt anfügen an die Liste "datenspeicher":

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 ist nicht Arbeit (die Funktion verhält sich wie eine leere generator).

Bin ich etwas fehlt?
Gibt es eine Möglichkeit, schalten Sie die oben genannten rekursiven Algorithmus in einen generator , ohne Sie zu ersetzen mit einem iterativen man?

InformationsquelleAutor der Frage Federico A. Ramponi | 2008-10-29

  1. 117
    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

    InformationsquelleAutor der Antwort Markus Jarderot

  2. 28

    Dies vermeidet die len(string)-Tiefe der Rekursion, und ist im Allgemeinen eine schöne Art und Weise zu handhaben Generatoren-innen-Generatoren:

    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, auch weiterhin Fortschritte in einem anderen generator, indem Sie einfach yielding es, statt des Durchlaufens und yielding jedem Element manuell.

    Python 3.3 hinzufügen Ertrag der syntax, die es erlaubt, Natürliche delegation zu einem sub-generator:

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

    InformationsquelleAutor der Antwort ephemient

  3. 19

    Den inneren Ruf, getPermutations-es ist ein generator, zu.

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

    Müssen Sie Durchlaufen, die mit einer for-Schleife (siehe @MizardX posting, das kantige mir aus von Sekunden!)

    InformationsquelleAutor der Antwort S.Lott

Schreibe einen Kommentar