Discussion :

[Linkau]

Hey tout le monde ^^,

Pour un projet je dois �crire une fonction qui prend en param�tres une liste de pi�ces unique (ex : [4,3,3,1,1]) et un montant (ex:6) et renvoie la liste des pi�ces utilis�s.

Du coup pour l'instant j'ai r�ussis � faire l'aglo glouton mais pour l'optimal je gal�re un peu plus (ex: pour l'instant pour la liste d'avant je trouvais la liste [4,1,1] alors qu'il faudrait trouver [3,3])

Voila pour mon probl�me si vous avez des questions

Merci d'avance pour vos r�ponses

[charliemtx]

Bonjour,

Pouvez-vous joindre le code que vous avez d�j� fait pour que l'on puisse vous aiguiller au mieux ?

[Linkau]

Code :

S�lectionner tout - Visualiser dans une fen�tre � part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
def rendreMonnaieGlouton(n, s):
    ret = []
 
    if n == 0:
        return ret
    if len(s) == 0:
        return None
 
    sbis = list(s)
    while len(sbis) != 0:
        #on prend la valeur la plus grande du tableau
        maxVal = max(sbis)
        iMaxVal = s.index(maxVal)
 
        sbis.remove(maxVal)
        p = s.pop(iMaxVal)
 
        if p == n:
            ret.append(p)
            s.append(p)
            return ret
        else:
            if p > n:
                s.append(p)
                continue
            else:
                ret.append(p)
                res = rendreMonnaieGlouton(n-p, s)
                s.append(p)
                if res != None:
                    for x in res:
                        ret.append(x)
                    return ret
                else :
                    return None
    return None

Voila pour l'algo glouton apr�s il y a surement bien plus simple ^^'

[charliemtx]

1) Etant donn� que la fonction doit retourner une liste, j'aurais retourn� des [] � la place des None (c'est pinaillage) ; j'aurais �galement ajout� (par exemple) � la places None (quand le total demand� est 0, ou inf�rieur � la plus petite des pi�ces existante) :

Code :

S�lectionner tout - Visualiser dans une fen�tre � part

raise ValueError :

2) La boucle index�e sur la longueur de sbis me semble �trange... je pense qu'il faut tout refaire, ne serait-ce parce qu'il y a une erreur de raisonnement dans le fait de forc�ment prendre la plus haute valeur en pi�ces dans le rendu final ; votre exemple en est la preuve.
Je crois qu'il faut essayer avec toutes les valeurs de pi�ces, la meilleure combinaison compos�e de pi�ces de valeur inf�rieur ; parmi toutes ces combinaisons, retourner celle qui a le plus petit nombre d'�l�ments

[lg_53]

On peut faire un algo qui est celui que la boulang�re applique lorsqu'elle nous rend la monnaie. Ca va nous donner une solution au probl�me "je donne quoi comme pi�ces pour faire X euros".

Maintenant ce que vous introduisez dans votre question, c'est le mot "optimal". Ca veut dire quoi optimal ? Il faut pr�ciser, car ca peut �tre optimal selon plein de crit�re diff�rent !

Bon l� de ce que je devine, optimal voudrait dire avec le moins de pi�ces possibles. Mais du coup ca reste une optimisation. Donc soit vous adoptez :
- un algorithme qui va parcourir exhaustivement toutes les solutions pour identifier � cout s�r la meilleure
- un qui va ne faire qu'un nombre limit� d'�valuation, mais qui va vous sortir une solution qui sera seulement localement optimale. Ca veut dire que si vous modifier un peu la solution, alors vous aurez forc�ment une solution moins bonne. Mais ca ne veut pas dire qu'il n'existe pas de meilleures solutions que celle trouv�e, solution qui pourrait etre radicalement diff�rente.

L� au vu de la taille de votre probl�me, ce n'est pas tr�s couteux d'examiner toutes les possibilit�s.
Vous les examiner toutes, ne retenez que celles qui sont solutions (� mettre dans une liste par exemple), et apr�s sur cette liste, vous identifier la possibilit� la plus courte (i.e. avec le moins de pi�ces).

Et apr�s, � vous de voir :
1) qu'est ce qu'on retourne s'il y a plusieurs solutions avec le meme nombre pieces ?
2) qu'est ce qu'on fait s'il n'y a pas de solutions ? Comment d�tecter ca ?
3) est ce qu'on traite les 2 questions pr�c�dentes, ou est ce qu'on suppose que ce qui est donn� � la fonction admet une solution, et que celle-ci est unique ? (chose que math�matiques on fait souvent, mais informatiquement ce n'est en g�n�ral pas une bonne id�e)

[Sve@r]

Salut

Du coup pour l'instant j'ai r�ussis � faire l'aglo glouton

D�sol�, ton algo ne fonctionne pas si on entre 6 avec [4, 3, 3, 1]. En prenant la pi�ce la plus grosse (ici 4) tu entres dans un cul de sac.
Il te faut partir sur l'id�e de lg_53, � savoir calculer toutes les solutions et ensuite extraire 1) celle qui donne un r�sultat et �ventuellement 2) celle qui correspond � l'id�e que tu te fais d'une optimisation.

Voila pour l'algo glouton apr�s il y a surement bien plus simple ^^'

Ca peut se faire...

Code python :

S�lectionner tout - Visualiser dans une fen�tre � part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import itertools
 
def rendreMonnaie(n, s):
	yield from sorted(
		set(
			y for y in (
				x\
				for i in range(1, len(s) + 1)\
				for x in itertools.combinations(s, i)
			) if sum(y) == n
		),
		key=lambda x: len(x),
	)
# rendreMonnaie()
 
for m in rendreMonnaie(6, [4, 3, 3, 3, 1, 1, 6]):
	print(m)

[marco056]

Houmpff ! M�me apr�s qqs ann�es de pratique, je n'y comprends rien : pas � la port�e du premier d�butant venu

[Sve@r]

Houmpff ! M�me apr�s qqs ann�es de pratique, je n'y comprends rien : pas � la port�e du premier d�butant venu

R��cris la comprehension list sous forme de boucle standard

Code python :

S�lectionner tout - Visualiser dans une fen�tre � part

1
2
3
for i in range(1, len(s) + 1):
	for x in itertools.combinations(s, i):
		print(x)

C'est de l� que je suis parti. Donc de l� tu verras le principe utilis� et pourras en d�duire le reste

[marco056]

Oui, enfin avec des set, yield et autres sorted(key lambda) c'est quand m�me du haut niveau.
J'ai des choses � comprendre bien avant cela.

[charliemtx]

Oui, enfin avec des set, yield et autres sorted(key lambda) c'est quand m�me du haut niveau.

Et non justement ! Ce sont des fondamentaux. Le bon niveau c'est au minimum de comprendre � quoi servent ses fonctions, le haut niveau c'est savoir quand les utiliser intelligemment

J'ai des choses � comprendre bien avant cela.

Je dirai au contraire que �a vaut le coup de prendre quelques minutes, ou quelques heures selon votre niveau, de comprendre ces notions ; un exemple tout b�te : moi-m�me.
Je suis un pur autodidacte et j'ai commenc� au travers de ma formation � la fac avec Matlab. Quand j'ai commenc� � coder en python, je ne jurai que par le module NumPy et ses arrays... sans m�me conna�tre les listes ! Lorsque j'ai commenc� � creuser, je me suis rendu compte de tout le boulot que j'avais pour rien avec mes arrays

[marco056]

Et non justement ! Ce sont des fondamentaux. Le bon niveau c'est au minimum de comprendre � quoi servent ses fonctions, le haut niveau c'est savoir quand les utiliser intelligemment



Je dirai au contraire que �a vaut le coup de prendre quelques minutes, ou quelques heures selon votre niveau, de comprendre ces notions ; un exemple tout b�te : moi-m�me.
Je suis un pur autodidacte et j'ai commenc� au travers de ma formation � la fac avec Matlab. Quand j'ai commenc� � coder en python, je ne jurai que par le module NumPy et ses arrays... sans m�me conna�tre les listes ! Lorsque j'ai commenc� � creuser, je me suis rendu compte de tout le boulot que j'avais pour rien avec mes arrays

Disons que dans mon boulot, je n'en ai pas besoin et que pour les loisirs, j'ai d'autres occupations.
J'aime bien creuser et je le ferai sans doute si j'ai le temps, pourquoi pas cet �t� ?

[Linkau]

Whoaah, merci pour toutes vos r�ponses je vais essayer de les analyser et je reviendrais vers vous si j'ai des questions

[tyrtamos]

Bonjour,

J'arrive certainement un peu tard, mais �a fait pas mal de temps que ce probl�me de rendre la monnaie m'intrigue, et j'ai creus� un peu.

Ma solution est moins �l�gante que celle de Sve@r (waouh...), mais je la comprends beaucoup mieux...

Son principe est simple:
- la structure de la caisse est celle-ci pour reprendre l'exemple du PO: C = [[4, 1], [3, 2],[1, 2]]. J'ai donc 1 pi�ce de 4� (qui n'existe pas), 2 pi�ces de 3� (pareil), et 2 pi�ces de 1�
- pour rendre la monnaie sur 6�, par exemple, l'algorithme commence � 4� et cherche � atteindre le rendu exact en prenant le plus de pi�ces de plus forte valeur.
- bien s�r, dans ces essais, il faudra revenir en arri�re quand on arrive � des r�sultats trop forts. Par exemple, 4�+3�=7: trop fort pour 6� => on annule le dernier 3� et on recommence avec 1�.
- en faisant comme �a, on trouve la 1�re solution [4, 1, 1]
- S'il y a une solution, l'algorithme en cherche une autre, en commen�ant cette fois par la pi�ce plus petite que 4�: 3�. Et on trouve une 2�me solution: [3, 3]
- � la fin, on cherche la meilleure solution en les triant selon le nombre de pi�ces rendues, et on prend la solution ayant le moins de pi�ces. Ici, ce sera: [3, 3]

Voil� la fonction largement comment�e:

Code :

S�lectionner tout - Visualiser dans une fen�tre � part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
def rendumonnaie(C=[], arendre=0):
    """Rendre la monnaie
       - C: argent en caisse. Ex: C[..., [2, 5], ...] => 5 pièces de 2€
       - arendre: valeur pour la monnaie à rendre
       Retourne la liste des pièces à rendre
    """
    if arendre > sum([p*n for p, n in C]) or arendre < C[-1][0]:
        yield [] # arendre trop grand ou trop petit: impossible
 
    M = [] # future liste de la monnaie à rendre
 
    ic0 = 0 # indice de départ de la pièce dans la caisse
    while C[ic0][0] > arendre:
        ic0 += 1 # on ne commence pas avec 2€ pour rendre la monnaie sur 1€!
 
    ic = ic0 # indice en cours de la pièce dans la caisse C
    jc = 0# indice en cours de la pièce en fonction du nb de pièces
    v = 0 # valeur du rendu en cours
    while True:
        # tentative d'ajout de la pièce en cours ic
        v += C[ic][0]
        M.append(C[ic][0])
        if v == arendre:
            # on a une solution
            yield  M
            # recherche d'une autre solution en démarrant à la pièce suivante
            ic0 += 1
            if ic0 > len(C)-1:
                break # Pas d'autre solution
            ic = ic0
            jc = 0
            M = []
            v = 0
        elif v > arendre:
            # on ne peut pas rendre trop: retour en arrière
            # annulation dernier ajout
            v -= C[ic][0] 
            M.pop(-1)
            # prendre plus petit si c'est possible
            ic += 1 # pièce suivante plus petite
            jc = 0 # 1er indice de cette pièce
            if ic > len(C)-1:
                # plus de pièce à essayer => pas de solution
                break
        else: 
            # v < arendre: on n'a pas encore atteint la somme à rendre
            # préparer l'ajout d'une autre même pièce'il y en a encore
            jc += 1
            if jc > C[ic][1]-1:
                # on a plus de pièce de cette valeur
                ic += 1 # pièce suivante plus petite
                jc = 0 # 1er indice de cette piècee
                if ic > len(C)-1:
                    # plus de pièce à essayer => pas de solution
                    break 
    yield []

Application pour l'exemple du PO:

Code :

S�lectionner tout - Visualiser dans une fen�tre � part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
C =  [[4, 1], [3, 2],[1, 2]]
arendre = 6
 
R = [] # liste des solutions
print("à rendre=", arendre)
for M in rendumonnaie(C, arendre):
    if len(M) > 0:
        print("Solution:", M)
        R.append(M)
if len(R)==0:
    print("Aucune solution")
else:    
    print()
    MS = sorted(R, key=lambda v: len(v))[0]
    print("Meilleure solution:", MS)

Ce qui donne:

Code :

S�lectionner tout - Visualiser dans une fen�tre � part

1
2
3
4
5
à rendre= 6
Solution: [4, 1, 1]
Solution: [3, 3]
 
Meilleure solution: [3, 3]

On peut tester des solutions plus complexes. Par exemple, une caisse plus fournie (on raisonne en centimes ici):
C = [[200, 5], [100, 5], [50, 20], [20, 7], [10, 12], [5, 20], [2, 5]]

On voit que comme on n'a pas de 1 centimes, il y aura des valeurs � rendre impossibles.

Et on peut tester l'algorithme sur toutes les valeurs � rendre, entre les limites:
C[-1][0] puisqu'on ne peut pas esp�rer rendre la monnaie sur 1 centimes quand la caisse n'en comporte pas. Ici, ce sera 2.
sum([p*n for p, n in C]) puisqu'on ne peut pas rendre la monnaie sur une somme qui d�passe la valeur totale de la caisse. Ici, ce sera 2870.

Code :

S�lectionner tout - Visualiser dans une fen�tre � part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
C =  [[200, 5], [100, 5], [50, 20], [20, 7], [10, 12], [5, 20], [2, 5]]
 
for arendre in range(C[-1][0], sum([p*n for p, n in C])+1):
    R = [] # liste des solutions pour arendre
    print("="*80)
    print("à rendre=", arendre)
    for M in rendumonnaie(C, arendre):
        if len(M) > 0:
            print("Solution:", M)
            R.append(M)
    if len(R)==0:
        print("Aucune solution")
    else:    
        print()
        MS = sorted(R, key=lambda v: len(v))[0]
        print("Meilleure solution:", MS)

Pour cette caisse, on trouve par exemple des solutions comme:

Code :

S�lectionner tout - Visualiser dans une fen�tre � part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
...
 
================================================================================
à rendre= 10
Solution: [10]
Solution: [5, 5]
Solution: [2, 2, 2, 2, 2]
 
Meilleure solution: [10]
================================================================================
à rendre= 11
Aucune solution
================================================================================
à rendre= 12
Solution: [10, 2]
Solution: [5, 5, 2]
 
Meilleure solution: [10, 2]
 
...
 
================================================================================
à rendre= 351
Aucune solution
================================================================================
à rendre= 352
Solution: [200, 100, 50, 2]
Solution: [100, 100, 100, 50, 2]
Solution: [50, 50, 50, 50, 50, 50, 50, 2]
Solution: [20, 20, 20, 20, 20, 20, 20, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 2]
 
Meilleure solution: [200, 100, 50, 2]
 
...

M�me pour des caisses assez complexes, cet algorithme est tr�s rapide. Je crois que l'on trouve toutes les solutions, mais je ne l'ai pas v�rifi� (il faudrait calculer toutes les combinaisons possibles).

En tout cas, c'�tait tr�s amusant � faire: merci au PO Linkau!

[Sve@r]

M�me pour des caisses assez complexes, cet algorithme est tr�s rapide. Je crois que l'on trouve toutes les solutions

Ben malheureusement non. Comme pour Linkau ton algorithme ne fonctionne pas si on entre 4, 3, 3, 1 (ou dans ta notation (4, 1), (3, 2), (1, 1)) avec � rendre 6. L� o� n'importe quelle boulang�re rendra 3+3, ton algo s'est focalis� sur 4 puis n'a pas su surmonter l'erreur. Toutefois (chose bizarre) en entrant (4, 1), (3, 2), (1, 2) l� il a trouv� 4+1+1 et aussi 3+3.

[wiztricks]

On peut tester des solutions plus complexes. Par exemple, une caisse plus fournie (on raisonne en centimes ici):
C = [[200, 5], [100, 5], [50, 20], [20, 7], [10, 12], [5, 20], [2, 5]]

Avec le syst�me de monnaie de l'euro, la premi�re solution trouv�e par l'algorithme glouton sera optimale (c�t� nombre de pi�ces): c'est un syst�me canonique.

Sinon dans le cas g�n�ral, c'est un probl�me NP-complet (il n'existe pas d'algo optimal).

- W

[tyrtamos]

Bonjour

Ben malheureusement non. Comme pour Linkau ton algorithme ne fonctionne pas si on entre 4, 3, 3, 1 (ou dans ta notation (4, 1), (3, 2), (1, 1)) avec � rendre 6. L� o� n'importe quelle boulang�re rendra 3+3, ton algo s'est focalis� sur 4 puis n'a pas su surmonter l'erreur. Toutefois (chose bizarre) en entrant (4, 1), (3, 2), (1, 2) l� il a trouv� 4+1+1 et aussi 3+3.

Pas d'accord! Il n'est pas dit que la meilleure solution devrait �tre la 1�re trouv�e (m�me si c'est fr�quent)! Et dans l'exemple du PO, la solution [3,3] n'a pas �t� trouv�e par hasard, mais gr�ce � l'algorithme, et j'ai expliqu� comment.


De wiztricks:

Sinon dans le cas g�n�ral, c'est un probl�me NP-complet (il n'existe pas d'algo optimal)

Merci, je ne savais pas. Et heureusement, parce que je n'aurais peut-�tre pas commenc� .

[Sve@r]

Pas d'accord! Il n'est pas dit que la meilleure solution devrait �tre la 1�re trouv�e (m�me si c'est fr�quent)! Et dans l'exemple du PO, la solution [3,3] n'a pas �t� trouv�e par hasard, mais gr�ce � l'algorithme, et j'ai expliqu� comment.

Tu n'as pas bien compris: ton programme ne fonctionne pas si on lui demande de trouver 6 avec les pi�ces 4, 3, 3 et 1. Dans ce cas il retourne une liste vide.

[tyrtamos]

Tu n'as pas bien compris: ton programme ne fonctionne pas si on lui demande de trouver 6 avec les pi�ces 4, 3, 3 et 1. Dans ce cas il retourne une liste vide.

Chez moi, il fonctionne parfaitement, et les r�sultats que j'ai mis dans mon message sont un simple copier-coller des r�sultats.

Avec:

Code :

S�lectionner tout - Visualiser dans une fen�tre � part

1
2
C =  [[4, 1], [3, 2],[1, 2]]
arendre = 6

(attention: tu dis [4,3,3,1] mais c'est [4,3,3,1,1])

et le petit code d'appel que j'ai donn�, �a affiche:

Code :

S�lectionner tout - Visualiser dans une fen�tre � part

1
2
3
4
5
à rendre= 6
Solution: [4, 1, 1]
Solution: [3, 3]
 
Meilleure solution: [3, 3]

Il faut trouver pourquoi �a ne marche pas chez toi. Chez moi: Python 3.7.8 sur Windows 10.

[Sve@r]

(attention: tu dis [4,3,3,1] mais c'est [4,3,3,1,1])

Justement, c'est bel et bien 4, 3, 3 et 1 (4 pi�ces dont une seule de 1) que je lui passe. Comme l'algorithme glouton de Linkau ne pouvait pas fonctionner avec cette configuration (cf mon premier post), j'ai voulu aussi la tester sur ton code.

[tyrtamos]

Justement, c'est bel et bien 4, 3, 3 et 1 (4 pi�ces dont une seule de 1) que je lui passe. Comme l'algorithme glouton de Linkau ne pouvait pas fonctionner avec cette configuration (cf mon premier post), j'ai voulu aussi la tester sur ton code.

Je n'avais pas vu cette configuration. Je l'ai essay�e et... tu as raison! J'ai compris pourquoi, et j'ai corrig� mon algorithme.

La raison est la suivante.
- au d�part, je commence par ic0=4�, et je cherche jusqu'� ce que la derni�re pi�ce soit essay�e.
- s'il n'y a pas de solution, �a retourne [].
- Il faut apr�s essayer en partant de ic0=3� (la pi�ce suivante), mais mon code pr�c�dent n'engageait cette possibilit� que si la 1�re tentative �tait r�ussie! Ce qui �tait une erreur manifestement. Maintenant, on cherche jusqu'� ce que ic0 arrive � la derni�re pi�ce et pas seulement ic.

Maintenant, avec

Code :

S�lectionner tout - Visualiser dans une fen�tre � part

1
2
C =  [[4, 1], [3, 2],[1, 1]]
arendre = 6

�a donne:

Code :

S�lectionner tout - Visualiser dans une fen�tre � part

1
2
3
4
à rendre= 6
Solution: [3, 3]
 
Meilleure solution: [3, 3]

Voil� le code corrig�:

Code :

S�lectionner tout - Visualiser dans une fen�tre � part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
from operator import itemgetter 
 
def rendumonnaie(C=[], arendre=0):
    """Rendre la monnaie
       - C: argent en caisse. Ex: C[..., [2, 5], ...] => 5 pièces de 2€
       ' arendre: valeur de la monnaie à rendre
       Retourne la liste des pièces à rendre
    """
    # Etre sûr que les valeurs de la caisse sont dans le bon ordre
    C.sort(key=itemgetter(0), reverse=True)
 
    if arendre > sum(p*n for p, n in C) or arendre < C[-1][0]:
        yield [] # arendre trop grand ou trop petit: impossible
 
    M = [] # future liste de la monnaie à rendre
 
    ic0 = 0 # indice de départ de la pièce dans la caisse
    while C[ic0][0] > arendre:
        ic0 += 1 # on ne commence pas avec 2€ pour rendre la monnaie sur 1€!
 
    ic = ic0 # indice en cours de la pièce dans la caisse C
    jc = 0# indice en cours de la pièce en fonction du nb de pièces
    v = 0 # valeur du rendu en cours
    while True:
        # tentative d'ajout de la pièce en cours ic
        v += C[ic][0]
        M.append(C[ic][0])
        if v == arendre:
            # on a une solution
            yield  M
            # recherche d'une autre solution en démarrant à la pièce suivante
            ic0 += 1
            if ic0 > len(C)-1:
                break # => on a fini
            ic = ic0
            jc = 0
            M = []
            v = 0
        elif v > arendre:
            # on ne peut pas rendre trop: retour en arrière
            # annulation dernier ajout
            v -= C[ic][0] 
            M.pop(-1)
            # prendre plus petit si c'est possible
            ic += 1 # pièce suivante plus petite
            jc = 0 # 1er indice de cette pièce
            if ic > len(C)-1:
                # fin de cet essai
                # recherche d'une autre solution en démarrant à la pièce suivante
                ic0 += 1
                if ic0 > len(C)-1:
                    break # => on a fini
                ic = ic0
                jc = 0
                M = []
                v = 0
        else: 
            # v < arendre: on n'a pas encore atteint la somme à rendre
            # préparer l'ajout d'une autre même pièce'il y en a encore
            jc += 1
            if jc > C[ic][1]-1:
                # on a plus de pièce de cette valeur
                ic += 1 # pièce suivante plus petite
                jc = 0 # 1er indice de cette piècee
                if ic > len(C)-1:
                    # fin de cet essai
                    # recherche d'une autre solution en démarrant à la pièce suivante
                    ic0 += 1
                    if ic0 > len(C)-1:
                        break # => on a fini
                    ic = ic0
                    jc = 0
                    M = []
                    v = 0
    yield []

Merci pour ta remarque!

[Edit]: deux petites am�liorations du code sans cons�quence sur les r�sultats: ajout d'un tri de C au d�but de la fonction (+ importation de itemgetter), et modification de l'argument de sum(): remplacement d'une list compr�hension par un g�n�rateur.