Générateurs récursifs en Python

Question

J'ai écrit une fonction pour retourner un générateur contenant chaque combinaison unique de sous-chaînes d'une longueur donnée qui contiennent plus de n éléments d'une chaîne primaire.

À titre d'exemple :

si j'ai 'abcdefghi' et une sonde de longueur deux, et un seuil de 4 éléments par liste, je voudrais obtenir.. :

['ab', 'cd', 'ef', 'gh']
['ab', 'de', 'fg', 'hi']
['bc', 'de', 'fg', 'hi']

Ma première tentative pour résoudre ce problème consistait à renvoyer une liste de listes. Cela a fini par faire déborder la mémoire de l'ordinateur. Comme solution secondaire grossière, j'ai créé un générateur qui fait quelque chose de similaire. Le problème est que j'ai créé un générateur imbriqué qui s'appelle lui-même. Lorsque j'exécute cette fonction, elle semble simplement tourner autour de la boucle for interne sans se rappeler elle-même. Je pensais qu'un générateur irait aussi loin que nécessaire dans le trou de la récursion jusqu'à ce qu'il atteigne l'instruction yield. Avez-vous une idée de ce qui se passe ?

def get_next_probe(self, current_probe_list, probes, unit_length):
    if isinstance(current_probe_list, list):
        last_probe=current_probe_list[-1]
        available_probes = [candidate for candidate in probes if candidate.start>last_probe.end]
    else:
        available_probes = [candidate for candidate in probes if candidate.start<unit_length]

    if available_probes:

        max_position=min([probe.end for probe in available_probes])
        available_probes2=[probe for probe in available_probes if max_position+1>probe.start]

        for new_last_probe in available_probes2:
            new_list=list(current_probe_list)
            new_list.append(new_last_probe)
            self.get_next_probe(new_list, probes, unit_length)

    else:
        if len(current_probe_list)>=self.num_units:
            yield current_probe_list

Si le rendement est changé en impression, cela fonctionne très bien ! J'apprécierais toute aide que je pourrais obtenir. Je réalise que ce n'est pas une implémentation optimale de ce type de problème de recherche, il semble que renvoyer une liste de positions trouvées à partir du dernier appel de get_next_probe et filtrer cette liste pour les éléments qui ne chevauchent pas new_last_probe.end serait beaucoup plus efficace... mais ceci était beaucoup plus facile à écrire pour moi. Tout apport d'algorithme serait quand même apprécié.

Gracias.

Answer 1

Je pensais qu'un générateur irait aussi loin que nécessaire dans le trou de la récursion jusqu'à ce qu'il atteigne l'instruction "yield".

La récursion se fera bien, mais pour obtenir le fichier yield pour qu'elle soit propagée vers l'extérieur, vous devez le faire explicitement, comme s'il s'agissait d'une valeur de type return vous devez explicitement return le résultat de chaque récursion. Donc, au lieu de :

 self.get_next_probe(new_list, probes, unit_length)

Vous feriez quelque chose comme :

 for val in self.get_next_probe(new_list, probes, unit_length):
     yield val

Si vous utilisez Python 3.3 ou une version plus récente, vous pouvez également procéder ainsi :

yield from self.get_next_probe(new_list, probes, unit_length)