Python: en utilisant un algorithme récursif comme un générateur

Question

Récemment j'ai écrit une fonction pour générer certaines séquences avec des contraintes non triviaux. Le problème est venu avec une solution récursive naturelle. Maintenant, il arrive que, même pour une entrée relativement petite, les séquences sont plusieurs milliers, donc je préférerais utiliser mon algorithme comme générateur au lieu de l'utiliser pour remplir une liste avec toutes les séquences.

Voici un exemple. Supposons que nous voulions calculer toutes les permutations d'une chaîne avec une fonction récursive. L'algorithme naïf suivant prend un « stockage » argument supplémentaire et une permutation ajoute chaque fois qu'il en trouve un:

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 

(. S'il vous plaît ne se soucient pas de l'inefficacité, ce n'est un exemple)

maintenant Je veux tourner ma fonction dans un générateur, soit pour donner une permutation au lieu d'ajouter à la liste de stockage:

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 

Ce code ne pas travail (la fonction se comporte comme un générateur vide).

Ai-je raté quelque chose? Y at-il un moyen de transformer l'algorithme récursif ci-dessus dans un générateur sans le remplacer par un itérative un?

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 

ou sans accumulateur:

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

L'appel intérieur à getPermutations - c'est un générateur, aussi.

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

Vous devez itérer que, avec une boucle for (voir l'affichage @MizardX, qui m'a devancé par seconde!)

Answer 3

On évite ainsi la récursion len(string) de -deep, et est en général une belle façon de gérer des générateurs à l'intérieur de générateurs:

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 nous permet de continuer à progresser dans un autre générateur simplement yield ing, au lieu de itérer et yield chaque élément manuellement ing.

---

Python 3.3 ajoutera yield from à la syntaxe, ce qui permet une délégation naturelle à un sous-générateur:

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