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. Or il arrive que, même pour des entrées relativement petites, les séquences soient 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 "storage" et lui ajoute une permutation 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 (Veuillez ne pas vous soucier de l'inefficacité, ce n'est que 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="") : si len(string) == 1 : rendement préfixe + chaîne # <----- else : for i in range(len(string)) : getPermutations(string[:i]+string [i+1 :], préfixe+chaîne[i]) pour la permutation dans getPermutations("abcd") : permutation d'impression Ce code ne fonctionne pas ( la fonction se comporte comme un em générateur de pty).
Ai-je raté 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 ?