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 varios miles, por lo que preferiría usar mi algoritmo como generador en lugar de usarlo para llenar una lista con todas las secuencias.
Aquí está 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 una:
def getPermutations(cadena, almacenamiento, prefijo=""): if len(cadena) == 1: almacenamiento.agregar(prefijo + cadena) # <----- más: for i in range(len(cadena)): getPermutations(cadena[:i]+cadena[i+1:], almacenamiento , prefijo+cadena[i]) almacenamiento = [] getPermutations("abcd", almacenamiento) para permutación en almacenamiento: imprimir permutación (No se preocupe por la ineficiencia, esto es solo un ejemplo.)
Ahora quiero convertir mi función en un generador, es decir, producir una permutación en lugar de agregarla 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:], prefijo+cadena[i]) para permutación en getPermutations("abcd"): imprimir permutación Este código no funciona ( la función se comporta como un em generador de pty).
¿Me estoy perdiendo algo? ¿Hay alguna forma de convertir el algoritmo recursivo anterior en un generador sin reemplazarlo por uno iterativo?