Python: używanie algorytmu rekurencyjnego jako generatora

Niedawno napisałem funkcję do generowania pewnych sekwencji z nietrywialnymi ograniczeniami. Problem pojawił się z naturalnym rozwiązaniem rekurencyjnym. Teraz zdarza się, że nawet dla stosunkowo niewielkich danych wejściowych sekwencje są po kilka tysięcy, dlatego wolałbym użyć mojego algorytmu jako generatora, zamiast wypełniać listę wszystkimi sekwencjami.

Oto przykład. Załóżmy, że chcemy obliczyć wszystkie permutacje łańcucha z funkcją rekurencyjną. Poniższy naiwny algorytm pobiera dodatkowy argument `` pamięć '' i dołącza do niego permutację, gdy tylko ją znajdzie:

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

(Proszę nie przejmować się nieefektywnością, to tylko przykład).

Teraz chcę przekształcić moją funkcję w generator, tj. Aby uzyskać permutację zamiast dołączać ją do listy pamięci:

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

Ten kod nie działa (funkcja zachowuje się jak pusty generator).

Czy coś mi brakuje? Czy istnieje sposób na przekształcenie powyższego algorytmu rekurencyjnego w generator bez zastępowania go algorytmem iteracyjnym ?

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

Lub bez akumulatora:

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

Pozwala to uniknąć len(string)rekurencji -głębokiej i jest ogólnie dobrym sposobem obsługi generatorów-wewnątrz-generatorów:

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

flattenpozwala nam kontynuować postęp w innym generatorze, po prostu yieldgo używając, zamiast iterować go i yieldręcznie wprowadzać każdy element.

Python 3.3 doda yield fromdo składni, co pozwala na naturalną delegację do generatora podrzędnego:

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

Wywołanie wewnętrzne getPermutations - to też jest 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])  # <-----

Musisz to powtórzyć za pomocą pętli for (zobacz post na @MizardX, który wydłużył mnie o kilka sekund!)