Python: utiliser un algorithme récursif comme générateur

Récemment, j'ai écrit une fonction pour générer certaines séquences avec des contraintes non triviales. 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 soient de 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 argument supplémentaire `` stockage '' et lui ajoute une permutation 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

(Ne vous souciez pas de l'inefficacité, ce n'est qu'un exemple.)

Maintenant, je veux transformer ma fonction en générateur, c'est-à-dire produire une permutation au lieu de l'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 fonctionne pas (la fonction se comporte comme un générateur vide).

Est-ce que je manque quelque chose? Existe-t-il un moyen de transformer l'algorithme récursif ci-dessus en générateur sans le remplacer par un itératif ?

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

Cela évite la len(string)récursivité -deep, et est en général un bon moyen de gérer les générateurs à l'intérieur des 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

flattennous permet de continuer à progresser dans un autre générateur en l' yieldutilisant simplement , au lieu de l'itérer et de yieldchaque élément manuellement.

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

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

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 parcourir cela avec une boucle for (voir la publication de @MizardX, qui m'a fait sortir de quelques secondes!)