Python: usando um algoritmo recursivo como gerador

99

Recentemente, escrevi uma função para gerar certas sequências com restrições não triviais. O problema veio com uma solução recursiva natural. Agora acontece que, mesmo para uma entrada relativamente pequena, as sequências são de vários milhares, portanto, eu preferiria usar meu algoritmo como um gerador em vez de usá-lo para preencher uma lista com todas as sequências.

Aqui está um exemplo. Suponha que desejamos calcular todas as permutações de uma string com uma função recursiva. O seguinte algoritmo ingênuo pega um argumento extra 'armazenamento' e anexa uma permutação a ele sempre que encontra um:

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

(Não se preocupe com a ineficiência, este é apenas um exemplo.)

Agora, quero transformar minha função em um gerador, ou seja, produzir uma permutação em vez de anexá-la à lista de armazenamento:

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

Este código não funciona (a função se comporta como um gerador vazio).

Estou esquecendo de algo? Existe uma maneira de transformar o algoritmo recursivo acima em um gerador sem substituí-lo por um iterativo ?

Federico A. Ramponi
fonte

Respostas:

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

Ou sem um acumulador:

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
fonte
29
No Python 3.4, você pode substituir as duas últimas linhas por yield from getPermutations(string[:i] + string[i+1:]), que é mais eficiente de várias maneiras!
Manuel Ebert
1
Você ainda precisa construir o resultado de alguma forma. Usar yield fromexigiria que você usasse o argumento do acumulador ( prefix).
Markus Jarderot
Sugestão: Defina outro gerador que retorne string[i],string[:i]+string[i+1:]pares. Então seria:for letter,rest in first_letter_options(string): for perm in getPermuations(rest): yield letter+perm
Thomas Andrews
29

Isso evita a len(string)recursão -deep e, em geral, é uma boa maneira de lidar com generators-inside-generators:

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

flattennos permite continuar o progresso em outro gerador simplesmente yielddigitando-o, em vez de iterar por ele e yieldprocessar cada item manualmente.


O Python 3.3 adicionará yield fromà sintaxe, o que permite a delegação natural a um subgerador:

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])
efêmero
fonte
20

A chamada interna para getPermutations - é um gerador também.

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

Você precisa iterar por isso com um loop for (veja a postagem de @MizardX, que me ultrapassou em segundos!)

S.Lott
fonte