Python: utilizando un algoritmo recursivo como generador

Question

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 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 extra 'almacenamiento' y agrega una permutación a ella 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 se preocupan por la ineficiencia, esto es sólo un ejemplo)

Ahora Quiero convertir mi función en un generador, es decir, para producir una permutación en lugar de añadir 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 hace no trabajo (la función se comporta como un generador de vacío).

¿Echo de menos algo? ¿Hay alguna manera de convertir el algoritmo recursivo anterior en un generador sin reemplazarlo por uno iterativo?

Answer 1

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 

Answer 2

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

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

Usted necesita iterar por que con un bucle for (ver @MizardX publicación, lo que me superó por segundo!)

Answer 3

Esto evita la recursividad len(string) -Profunda, y es, en general, un buen manera de manejar generadores-dentro-generadores:

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 yield ing, en lugar de iteración a través de él y yield ing cada elemento manualmente.

---

Python 3.3 agregará yield from a la sintaxis, 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])