Python: usando un algoritmo recursivo como generador

Recientemente escribí una función para generar ciertas secuencias con restricciones no triviales. El problema vino con una solución recursiva natural. Ahora sucede que, incluso para una entrada relativamente pequeña, las secuencias son de varios miles, por lo que preferiría usar mi algoritmo como generador en lugar de usarlo para completar una lista con todas las secuencias.

Aquí hay un ejemplo. Supongamos que queremos calcular todas las permutaciones de una cadena con una función recursiva. El siguiente algoritmo ingenuo toma un argumento adicional ‘almacenamiento’ y le agrega una permutación cada vez que encuentra uno:

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, no te preocupes por la ineficiencia, esto es solo un ejemplo).

Ahora quiero convertir mi función en un generador, es decir, para obtener una permutación en lugar de anexarla a la lista de almacenamiento:

 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 no funciona (la función se comporta como un generador vacío).

¿Me estoy perdiendo de algo? ¿Hay alguna forma de convertir el algoritmo recursivo anterior en un generador sin reemplazarlo por uno iterativo ?

 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 

O sin un 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 

Esto evita la recursión profunda de len(string) y, en general, es una buena forma de manejar 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 

flatten nos permite continuar el progreso en otro generador simplemente cediéndolo, en lugar de iterarlo y generando cada elemento manualmente.


Python 3.3 agregará yield from a la syntax, lo que permite la delegación natural a un sub-generador:

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

La llamada interior a getPermutations – también es un generador.

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

Debe iterar todo eso con un bucle for (consulte la publicación de @MizardX, ¡lo que me eliminó en segundos!)