Python: używanie algorytmu rekurencyjnego jako generatora

99

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 ?

Federico A. Ramponi
źródło

Odpowiedzi:

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

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
Markus Jarderot
źródło
29
W Pythonie 3.4 możesz zamienić ostatnie dwie linie na yield from getPermutations(string[:i] + string[i+1:]), co jest bardziej wydajne na wiele sposobów!
Manuel Ebert
1
Nadal musiałbyś w jakiś sposób zbudować wynik. Użycie yield fromwymagałoby użycia argumentu akumulatora ( prefix).
Markus Jarderot
Sugestia: zdefiniuj inny generator, który zwraca string[i],string[:i]+string[i+1:]pary. Wtedy wyglądałoby to tak:for letter,rest in first_letter_options(string): for perm in getPermuations(rest): yield letter+perm
Thomas Andrews
29

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])
ephemient
źródło
20

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

S.Lott
źródło