Python: używanie algorytmu rekurencyjnego jako generatora

Ostatnio napisałem funkcję do generowania pewnych sekwencji z nietrywialnymi ograniczeniami. Problem pojawił się z naturalnym rozwiązaniem rekurencyjnym. Teraz zdarza się, że nawet przy stosunkowo małym wejściu sekwencje są kilka tysięcy, dlatego wolałbym użyć mojego algorytmu jako generatora, zamiast używać go do wypełniania listy wszystkimi sekwencjami.

Oto przykład. Załóżmy, że chcemy obliczyć wszystkie permutacje ciągu z funkcją rekurencyjną. Następujące naiwne algorytm pobiera dodatkowy argument "storage" i dodaje do niego permutację za każdym razem, gdy 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 dbać o nieefektywność, to tylko przykład.)

Teraz chcę przekształcić moją funkcję w generator, tzn. dać permutację zamiast dodawać 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 działa a nie (funkcja zachowuje się jak pusty generator).

Czy coś przeoczyłem? Czy istnieje sposób na odwrócenie powyższego rekurencyjnego algorytm do generatora bez zastępowania go iteracyjnym ?
Author: Federico A. Ramponi, 2008-10-30
Source

3 answers

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
 117
Author: Markus Jarderot,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2008-10-29 23:53:47

Pozwala to uniknąć len(string)-głębokiej rekurencji i jest ogólnie dobrym sposobem na obsługę 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

flatten pozwala nam kontynuować postęp w innym generatorze po prostu yielding it, zamiast iteracji przez niego i yielding każdy element ręcznie.

Python 3.3 doda yield from do składni, która pozwala na naturalną delegację do sub-generatora: 

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
Author: ephemient,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-08-13 12:29:36

/ Align = "center" bgcolor = "# e0ffe0 " / cesarz chin / / align = center / 

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 przez to przebrnąć za pomocą pętli for (patrz post @ MizardX, który mnie ominął o kilka sekund!)

 19
Author: S.Lott,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-02-15 22:01:54