Python: utiliser 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 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, je préférerais donc utiliser mon algorithme en tant que 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 avec une fonction récursive. L'algorithme naïf suivant utilise un argument supplémentaire 'storage' 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

(S'il vous plaît, 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 donner 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 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 ?

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

Ceci évite la récursion len (chaîne) -deep, et constitue en général un moyen agréable 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 poursuivre la progression dans un autre générateur en cédant , au lieu de le parcourir et de céder à chaque élément manuellement. .

Python 3.3 ajoutera cédant de à 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 pour obtenirPermutations - 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 distancé de quelques secondes!)