Python : utilisation d'un algorithme récursif comme générateur

Question

Récemment, j'ai écrit une fonction pour générer certaines séquences avec des contraintes non triviales. Le problème était accompagné d'une solution récursive naturelle. Or il se trouve 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 plutôt que 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 de caractères avec une fonction récursive. L'algorithme naïf suivant prend un argument supplémentaire "stockage" et ajoute une permutation à celui-ci chaque fois qu'il en trouve une :

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

Je veux maintenant 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 no fonctionnent (la fonction se comporte comme un générateur vide).

Est-ce que j'ai manqué quelque chose ? Y a-t-il un moyen de transformer l'algorithme récursif ci-dessus en un générateur sans la remplacer par une méthode itérative ?

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

Cela permet d'éviter le len(string) -récursion profonde, et c'est en général une bonne façon 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

flatten nous permet de continuer à progresser dans un autre générateur simplement en yield au lieu d'itérer à travers lui et de yield de chaque é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])

Answer 3

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 à travers cela avec une boucle for (voir le message de @MizardX, qui m'a devancé de quelques secondes !)