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 entradas relativamente pequenas, as sequências são vários milhares, então 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 queremos calcular todas as permutações de uma string com uma função recursiva. O algoritmo ingênuo a seguir recebe 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 (Por favor, não se importe com ineficiência, isso é apenas um exemplo.)
Agora eu 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]) para permutação em getPermutations("abcd"): imprima permutação Este código não funciona ( a função se comporta como um em gerador pty).
Está faltando alguma coisa? Existe uma maneira de transformar o algoritmo recursivo acima em um gerador sem substituí-lo por um iterativo?