utilisation yield pour algo récursif

Question

Je remonte un post qu'un certain @policier moustachu a posté sur l'article de S&M traitant des yield.
Et vu que le mec n'a jamais eu de réponse à sa question labàs en com's, je remonte sa question ici, de plus sa question avait l'air intéressante, j'aurai bien aimé connaître la suite des péripéties, espérons qu'ici elle trouvera sa place !

ça ressemble à ça :

policier moustachu 11/08/2014 at 14:58 Yo ! Je me suis fais un petit
algo récursif pour calculer toutes les combinaisons de n entiers dont
la somme fait m. Et pour pas exploser la pile je me demandais si
c’était possible d’utiliser yield. Mais c’est pas évident évident …

Edit d'indentation basée sur ça :

def pilepoile(n, taille):
    if taille == 1:
        return [[n]]
    else:
        toutes_les_listes = []
        for i in range(n + 1):
            intermediates = pilepoile(n-i, taille -1)
            for l in intermediates:
                l.insert(0,i)
            toutes_les_listes.extend(intermediates)
        return toutes_les_listes

la fonction pour utiliser l'algo est la suivante :

def affiche_sommes(n, taille):
    for i in pilepoile(n, taille):
       print(i)

Par exemple, si je veux la liste de 3 éléments dont la somme fait 2 je fais :

pilepoile(3,2)
>> [0, 0, 2], [0, 1, 1], [0, 2, 0], [1, 0, 1], [1, 1, 0], [2, 0, 0]]

Par exemple, si je veux la liste de 2 éléments dont la somme fait 10 je fais :

>>> pilepoile(10,2)
[[0, 10], [1, 9], [2, 8], [3, 7], [4, 6], [5, 5], [6, 4], [7, 3], [8, 2], [9, 1], [10, 0]]

Voici une explication détaillée de l'auteur:

pilepoile(10,3)
- J'essaie avec le premier élément égal à 1. Je dois maintenant trouver une liste de 2 éléments dont la somme est égal à 9. J'appelle
pilepoile(9,2)
- J'essaie avec le premier élément égal à 1. Je dois trouver une liste de 1 élément dont la somme est égal à 8. J'appelle
pilepoile(8,1)
- Une liste de 1 élément dont la somme est égal à 8 : [8]
[1, 8]
- Maintenant j'essaie avec le premier élément égal à 2. Je dois trouver une liste de 1 élément dont la somme est égal à 7.
J'appelle pilepoile(7,1) qui me renvoie 7
[2, 7]
- etc ...... [1, 1, 8] [1,2,7] [1,3,6][1,4,5] ................[1,9,0]

-J'essaie avec le premier élément égal à 2. Je dois maintenant trouver une liste de 2 éléments dont la somme est égal à 8. J'appelle
pilepoile(8,2) [.....] [2, 1, 7] [2,2,6] [2,3,5][2,4,4]
......[2,8,0]

En gros, la fonction pilepoile prend deux entrées, une pour la taille de la liste (taille), et l'autre pour le résultat (n) voulu calculée en faisant la somme de taille chiffres.

Comments

En effet, la question est intéressante.
Par contre, je pige pas le bout de code (outre la dernière ligne clairement mal indentée). J'ai essayé de le faire tourner et le résultat n'est pas correct.

---

Yép, j'édite ça ^^.
C'est juste que j'ai récup le code sans aucune indentation, j'ai juste imaginé ce que le mec a voulu dire/faire.
J'ai un doute sur l'indentation de l'avant-derniere ligne ^^

---

L'algo avec la bonne indentation est décrit là http://www.commentcamarche.net/forum/affich-30629957-programme-a-simplifier

Par contre je ne pense pas que ce soit des combinaisons, car il y a répétition.

---

Il manque encore une indentations sur les 4 dernieres lignes (la seconde liste est nested, le return est dans le else)

@boblinux, tu nous mettrais pas un petit exemple d'utilisation ?
La question est tres interessante, mais c'est relou d'avoir a deviner ce que fait du code copié collé mal indenté :)

---

@Benjamin @Jc
Merci pour les com's, j'ai entièrement édité le post, pense que maintenant c'est plus clair.

Answer 1

Je ne connais pas bien yield, mais voici ma tentative

def pilepoile(n, taille):
    if taille == 1:
        yield [n]
    else:
        for i in range(n+1):
            intermediates = pilepoile(n-i, taille-1)
            for l in intermediates:
                yield [i] + l

Comments

un exemple d'utilisation?

---

Je trouve ça élégant.

Et pour n'utiliser que des générateurs, tu peu remplacer range par xrange.

---

Pour reprendre ta fonction "affiche_sommes" et ton deuxième exemple

>>> affiche_sommes(10, 2)
[0, 10]
[1, 9]
[2, 8]
[3, 7]
[4, 6]
[5, 5]
[6, 4]
[7, 3]
[8, 2]
[9, 1]
[10, 0]

---

Pas mal, je pense qu'on a la réponse à notre question,
peut-on avoir aperçu de l'état de la pile avec et sans l'utilisation de yield?
(en éditant la réponse)
Histoire qu'on répondre à la problématique de l'auteur, à savoir :

Et pour pas exploser la pile

Answer 2

Pas tres tres exactement identique a la fonction initiale, mais j'ai ceci:

# script
from itertools import combinations, combinations_with_replacement
from itertools import permutations
from functools import reduce

def ppp(n, taille):
    if taille == 1: yield list(n)                                                                      
    else:
        #c = combinations(range(n+1), taille)                                                                           
        c = combinations_with_replacement(range(n+1), taille)
        for t in c:
           if sum(t) == n:
                for p in permutations(t):
                    yield list(p)

Dans une console:

>>> for i in ppp(10, 2): print(i)
... 
[0, 10]
[10, 0]
[1, 9]
[9, 1]
[2, 8]
[8, 2]
[3, 7]
[7, 3]
[4, 6]
[6, 4]
[5, 5]
[5, 5]
>>> 

Comments

Pas convaincu par

yield list(p)

qui va convertir le générateur des permutations en liste, donc les parcourir, donc générer toutes les combinaisons possibles a l'intérieur de la fonction ppp().

Pareil pour

    sum(t)

Du coup, ça perd son intérêt :)

---

@jc: Le yield list(p) peut/doit etre remplacé par un yield p, entierement d'accord. Pour le sum(t) vas-y, dis m'en plus.

---

Ton sum(t) va parcourir chaque tuple renvoyés par combinations_with_replacement au sein de ta fonction , ce que tu cherches a éviter au max quand tu yield.

(Au passage, je pensais que combinations_with_replacement renvoyait une liste d'itérateurs, ce n'est pas le cas)

---

@ptank

tu peux le cacher dans un premier temps, ensuite si le modo a envie il peut supprimer ton com's ^^

Answer 3

Ci joint avec un accumulateur:

def pile_poil(n,taille,acc=[]):
    if taille==1:
        yield acc+[n]
    else:
        for i in range(n+1):
            yield from pile_poil(n-i,taille-1,acc+[i])

def affiche_somme(n,taille):
    for i,liste in enumerate(pile_poil(n,taille)):
        print(i,liste,sum(liste))

affiche_somme(10,3)

Ca donne:

0 [0, 0, 10] 10
1 [0, 1, 9] 10
2 [0, 2, 8] 10
3 [0, 3, 7] 10
4 [0, 4, 6] 10
5 [0, 5, 5] 10
6 [0, 6, 4] 10
7 [0, 7, 3] 10
8 [0, 8, 2] 10
9 [0, 9, 1] 10
10 [0, 10, 0] 10
11 [1, 0, 9] 10
12 [1, 1, 8] 10
13 [1, 2, 7] 10
14 [1, 3, 6] 10
15 [1, 4, 5] 10
16 [1, 5, 4] 10
17 [1, 6, 3] 10
18 [1, 7, 2] 10
19 [1, 8, 1] 10
20 [1, 9, 0] 10
21 [2, 0, 8] 10
22 [2, 1, 7] 10
23 [2, 2, 6] 10
24 [2, 3, 5] 10
25 [2, 4, 4] 10
26 [2, 5, 3] 10
27 [2, 6, 2] 10
28 [2, 7, 1] 10
29 [2, 8, 0] 10
30 [3, 0, 7] 10
31 [3, 1, 6] 10
32 [3, 2, 5] 10
33 [3, 3, 4] 10
34 [3, 4, 3] 10
35 [3, 5, 2] 10
36 [3, 6, 1] 10
37 [3, 7, 0] 10
38 [4, 0, 6] 10
39 [4, 1, 5] 10
40 [4, 2, 4] 10
41 [4, 3, 3] 10
42 [4, 4, 2] 10
43 [4, 5, 1] 10
44 [4, 6, 0] 10
45 [5, 0, 5] 10
46 [5, 1, 4] 10
47 [5, 2, 3] 10
48 [5, 3, 2] 10
49 [5, 4, 1] 10
50 [5, 5, 0] 10
51 [6, 0, 4] 10
52 [6, 1, 3] 10
53 [6, 2, 2] 10
54 [6, 3, 1] 10
55 [6, 4, 0] 10
56 [7, 0, 3] 10
57 [7, 1, 2] 10
58 [7, 2, 1] 10
59 [7, 3, 0] 10
60 [8, 0, 2] 10
61 [8, 1, 1] 10
62 [8, 2, 0] 10
63 [9, 0, 1] 10
64 [9, 1, 0] 10
65 [10, 0, 0] 10

Answer 4

Bon ce n'est pas récursif et il n'y a pas de yield explicite mais j'ai quand même envie de le poster. Un générateur pour la liste des combinaisons :

from itertools import *

def pilepoile(n, taille):
    return (c 
            for c in combinations_with_replacement(range(n + 1), taille) 
            if sum(c) == n)

On obtient la liste des combinaisons :

>>> list(pilepoile(8, 2))
[(0, 8), (1, 7), (2, 6), (3, 5), (4, 4)]

Pour la liste des permutations :

def pilepoile2(n, taille):
    return (c 
            for c in product(*tee(range(n + 1), taille))
            if sum(c) == n)

Example :

>>> list(pilepoile2(8, 2))
[(0, 8), (1, 7), (2, 6), (3, 5), (4, 4), (5, 3), (6, 2), (7, 1), (8, 0)]