Discussion :

[Jobson01]

Bonjour à tous !

Jai grand besoin d'aide, je suis vraiment un gros débutant en python :

J'ai un dictionnaire avec les noms et les montants qui vont avec
Ex: dictionnaire= {"Raoul ": 2000, " Hermann":3000,"Victor ": 1500, " Paul":1000,"Michel": 2500, " Valérie":3000,"Bob": 2000, " Hermann":3000,"Raoul ": 500, "Ben":4000}

Je voudrais un code pour pouvoir afficher toutes les combinaisons clé/Valeur dont la somme des valeurs est égale à 5000.
Ex:
[Raoul : 2000, Hermann : 3000]
[Victor : 1500, Paul : 1000, Michel : 2500]
[Raoul :2000, Bob: 2000, Paul: 1000]
Etc.

Merci d'avance.
Cordialement !

[fred1599]

Bonjour,

Montrez au moins un début de code avec un de vos essais...

[MPython Alaplancha]

Bonjour.
Tu pourrais te servir de la fonction combinations du module itertools ...

[Sve@r]

Bonjour

Pour faire suite à la suggestion de MPython Alaplancha, il te faut boucler sur i de 1 à nb (inclus), sortir les combinaisons de (dico.keys(), i), les prendre une à une et ne sortir que celles où la somme fait 5000. Et fais gaffe, tu as deux "Raoul" dans ton dico.

PS: être débutant n'est absolument ni une excuse ni une justification de quoi que ce soit. On a tous été débutants et on a tous travaillé pour ne plus l'être.

[tyrtamos]

Bonjour

Un petit coup de pouce.

Il s'agit d'un problème classique de dénombrement: liste des parties d'un ensemble.

Mais avant tout, il faut corriger le dictionnaire donné: supprimer les espaces à gauche et à droite des noms, et corriger les doublons: le 2ème "Hermann" devient "Hermann2" et le 2ème "Raoul" devient "Raoul2". Il faut tout de même faire attention à ce genre de chose: l'informatique demande de la rigueur puisqu'il suffit d'une erreur d'un seul caractère pour qu'un programme ne marche pas... Voilà par exemple le dictionnaire corrigé:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
dico = {"Raoul": 2000, "Hermann":3000, "Victor": 1500, "Paul":1000,
        "Michel": 2500, "Valérie":3000, "Bob": 2000, "Hermann2":3000,
        "Raoul2": 500, "Ben":4000}

Il y a une solution que j'aime bien: s'appuyer sur les nombres binaires! En effet, si on a comme ici un dictionnaire de 10 personnes, on peut faire la liste des nombres binaires qui vont de 1 à 2**10-1, et ne considérer que les "1" avec leur index dans chacun de ces nombres.

On peut traduire le dictionnaire en liste, qui sera plus facile à manipuler:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

liste = list(dico.items())

Quand on fait la liste des nombres binaires de 1 à 2**len(liste)-1, on va trouver, par exemple le nombre 73, on le convertit en binaire bin(73) => "0b10010010", on supprime le "0b" devant avec bin(73)[2:] => 10010010, et on ne va considérer que les "1" avec leurs correspondance dans la liste:
le 1er "1" (indice 0) => "Raoul": 2000
le 2ème "1" (indice 3) => "Paul":1000
le 3ème "1" (indice 6) => "Bob": 2000

Comme la somme fait 5000, c'est un ensemble qu'il faut conserver.

Il faut tout de même corriger la liste des nombres binaires, puisque par exemple 10100000 et 101 donneront deux nombres, mais correspondent à la même composition. Il suffit d'ajouter des "0" à droite. Combien? le nombre binaire maxi sera ici de 2**10-1 soit 1023, et son binaire sera 0b1111111111. Il faudra donc que tous les nombres binaires soient complétés à droite par des "0" autant qu'il faut pour qu'ils aient 10 positions binaires (ou len(bin(2**10-1)[2:])).


Je m'arrête là pour le code (il faut qu'il reste un peu de travail au PO...), mais voilà ce qu'on trouve comme résultat:

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
Trouvé ! 1100000000 5000 [('Raoul', 2000), ('Hermann', 3000)]
Trouvé ! 1011000010 5000 [('Raoul', 2000), ('Victor', 1500), ('Paul', 1000), ('Raoul2', 500)]
Trouvé ! 1001001000 5000 [('Raoul', 2000), ('Paul', 1000), ('Bob', 2000)]
Trouvé ! 1000100010 5000 [('Raoul', 2000), ('Michel', 2500), ('Raoul2', 500)]
Trouvé ! 1000010000 5000 [('Raoul', 2000), ('Valérie', 3000)]
Trouvé ! 1000000100 5000 [('Raoul', 2000), ('Hermann2', 3000)]
Trouvé ! 0110000010 5000 [('Hermann', 3000), ('Victor', 1500), ('Raoul2', 500)]
Trouvé ! 0100001000 5000 [('Hermann', 3000), ('Bob', 2000)]
Trouvé ! 0011100000 5000 [('Victor', 1500), ('Paul', 1000), ('Michel', 2500)]
Trouvé ! 0011001010 5000 [('Victor', 1500), ('Paul', 1000), ('Bob', 2000), ('Raoul2', 500)]
Trouvé ! 0010010010 5000 [('Victor', 1500), ('Valérie', 3000), ('Raoul2', 500)]
Trouvé ! 0010000110 5000 [('Victor', 1500), ('Hermann2', 3000), ('Raoul2', 500)]
Trouvé ! 0001000001 5000 [('Paul', 1000), ('Ben', 4000)]
Trouvé ! 0000101010 5000 [('Michel', 2500), ('Bob', 2000), ('Raoul2', 500)]
Trouvé ! 0000011000 5000 [('Valérie', 3000), ('Bob', 2000)]
Trouvé ! 0000001100 5000 [('Bob', 2000), ('Hermann2', 3000)]

Bonne suite!

[User]

Bonjour à vous,

Est-ce que ce sont des données réelles ?

S'il y a plus de données on peut dans certains cas optimiser le code.

Par exemple, en classant les montants par ordre croissant :

500, 1000, 1500, 2000, 2000, 2500, 3000, 3000, 3000, 4000

avec les 4 premiers montants on a déjà :

500 + 1000 + 1500 + 2000 = 5000

donc ça ne sert à rien de chercher les combinaisons de 5, 6 ...

c'est une piste ..

Cdlt,

[Sve@r]

...puisque par exemple 10100000 et 101 donneront deux nombres, mais correspondent à la même composition. Il suffit d'ajouter des "0" à droite.

Plutôt à gauche non ? Ou alors plus simplement on numérote les indices à partir de la droite. Ainsi 101 ne pourra pas être confondu avec 10100000 et cela ne changera rien au résultat final.

[fred1599]

Salut,

Maintenant, j'aimerais bien voir une solution plus simple avec itertools!

Une proposition,

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
from itertools import combinations
 
def partiesliste(seq, limit=5000):
    resultats = []
    for r in range(len(seq) + 1):
        for combo in combinations(seq, r):
            if sum(item[1] for item in combo) == limit:
                resultats.append(combo)
    return resultats
 
liste = [('Raoul2', 500), ('Paul', 1000), ('Victor', 1500), ('Raoul', 2000),
         ('Bob', 2000), ('Michel', 2500), ('Hermann', 3000), ('Valérie', 3000),
         ('Hermann2', 3000), ('Ben', 4000)]
 
parties = partiesliste(liste)
for elem in parties:
 
    print(elem)

[tyrtamos]

Bonjour fred1599

Une proposition,

Un grand merci! Ça donne bien les bons résultats.

Je note tout de même que combinations est appelé autant de fois qu'il y a de sous-listes + 1 (11 ici). Le fait qu'il soit compilé lui donne-t-il encore un avantage dans ces conditions?

Ce qui m'étonne, c'est que ce problème de dénombrement a un caractère général, et je suis étonné qu'il n'y ait pas une seule fonction qui fasse ça dans itertools. Ou je ne l'ai pas trouvée?

[jurassic pork]

Hello,

Je note tout de même que combinations est appelé autant de fois qu'il y a de sous-listes + 1 (11 ici). Le fait qu'il soit compilé lui donne-t-il encore un avantage dans ces conditions?

j'ai fait un calcul de performance avec timeit pour vos fonctions partiesliste sur mon ordinateur avec un python 3.10.11 et voilà ce que cela donne :

=========calcul Tyrtamos ==========
The difference of time is : 0.001450499999918975
=========calcul Fred ==========
The difference of time is : 0.0005495000004884787

Ami calmant, J.P

[fred1599]

Ou je ne l'ai pas trouvée?

Non tu as raison, elle n'existe pas...

Mais je me dis que peut-être mieux que d'utiliser itertools et combinations serait la méthode du backtracking.

L'objectif est d'explorer toutes les combinaisons possibles en ajoutant un élément à la fois à la combinaison courante, tout en gardant la trace de leur somme cumulée. Si à n'importe quel point la somme cumulée dépasse la limite, la fonction revient en arrière (backtracks), évitant de tester d'autres combinaisons inutiles dans cette branche. Cela permet d'économiser beaucoup de temps en évitant d'examiner les combinaisons dont la somme ne peut pas potentiellement égaler la limite.

Pour cela on pourrait faire un traitement sur une séquence triée (par poids).

Je note tout de même que combinations est appelé autant de fois qu'il y a de sous-listes + 1 (11 ici).

Le fait que combinations soit compilé offre un avantage significatif en termes de performance pour la génération de combinaisons, mais dans un scénario où tu as besoin de filtrer activement les résultats en fonction de leurs propriétés (comme la somme des éléments), l'utilisation répétitive de cette fonction pourrait ne pas être optimale. Dans ces cas, une approche personnalisée avec backtracking pourrait être plus efficace.

[fred1599]

@jurassic_pork,

Merci, peux-tu pour raison de cohérence faire un test de temps pour le backtracking ?

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
def backtrack(seq, limit, index, current_combination, current_sum, resultats):
    if current_sum > limit:
        return None
    if current_sum == limit:
        resultats.append(current_combination)
        return None
    for i in range(index, len(seq)):
        backtrack(seq, limit, i + 1, current_combination + [seq[i]], current_sum + seq[i][1], resultats)
 
def partiesliste(seq, limit=5000):
    resultats = []
    seq.sort(key=lambda x: x[1], reverse=True)  # Tri par poids décroissant pour optimisation
    backtrack(seq, limit, 0, [], 0, resultats)
    return resultats
 
liste = [('Raoul2', 500), ('Paul', 1000), ('Victor', 1500), ('Raoul', 2000),
         ('Bob', 2000), ('Michel', 2500), ('Hermann', 3000), ('Valérie', 3000),
         ('Hermann2', 3000), ('Ben', 4000)]
 
parties = partiesliste(liste)
for elem in parties:
    print(elem)

[jurassic pork]

peux-tu pour raison de cohérence faire un test de temps pour le backtracking ?

voici ce que cela donne avec le backtrack :

=========calcul Fred Backtrack ==========
The difference of time is : 0.000550599997950485

[papajoker]

j'ai voulu un comparatif des 2 (as jurassic pork)

Mais pour être "plus réel", aussi générer en entrée plus grande, resultat ... la cata :

ps: avec liste = gen_liste(10, LIMIT) ok mais 40 personnes .

Avec 20 personnes, déjà une énorme dégradation ! (temps x par 200) et a chaque ajout ...

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
tyrtamos 0.010279538999384386
itertools 0.004732360999696539
 
20 personnes ...
tyrtamos 2.0467660060003254
itertools 1.2397259099998337
 
22 personnes ...
tyrtamos 9.151937398999507
itertools 5.3870852239997475
 
23 personnes ...
tyrtamos 18.633735909999814
itertools 10.896461121999891
 
24 personnes ...
tyrtamos 37.69059759399897
itertools 21.38697676800075
 
25 personnes ...
tyrtamos 80.54753221400097
itertools 46.278982055002416
 
300 personnes ...
^C KeyboardInterrupt

Dans 2 jours un résultat ?

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
76
77
78
79
80
81
82
import timeit
from itertools import combinations
from random import randrange
 
 
LIMIT = 5000
 
liste = [
    ('Raoul2', 500), ('Paul', 1000), ('Victor', 1500), ('Raoul', 2000),
    ('Bob', 2000), ('Michel', 2500), ('Hermann', 3000), ('Valérie', 3000),
    ('Hermann2', 3000), ('Ben', 4000)
]
 
def gen_liste(size=700, limit=LIMIT):
    results = []
    for i in range(size):
        v = f"personne_{i}", randrange(0, limit, 100)
        results.append(v)
    return results
 
 
def tyrtamos(liste, limit=LIMIT):
 
    def partiesliste(seq):
        """Calcule la liste des parties d'en ensemble.
        Exemple: si seq=[1,2,3], retourne:
                    [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
        """
        p = []
        i, imax = 0, 2**len(seq)-1
        while i <= imax:
            s = []
            j, jmax = 0, len(seq)-1
            while j <= jmax:
                if (i>>j)&1 == 1:
                    s.append(seq[j])
                j += 1
            p.append(s)
            i += 1
        return p
    result = partiesliste(liste)
    results = []
    for elem in result:
        s = 0
        for z in elem:
            s+=z[1]
        if s==limit:
            results.append(elem)
    return results
 
 
def itertools_combinations(liste, limit=5000):
 
    def partiesliste(seq, limit):
        resultats = []
        for r in range(len(seq) + 1):
            for combo in combinations(seq, r):
                if sum(item[1] for item in combo) == limit:
                    resultats.append(combo)
        return resultats
    return partiesliste(liste, limit)
 
 
print(liste)
print()
s =timeit.timeit(lambda: tyrtamos(liste), number=10)
print("tyrtamos", s)
s = timeit.timeit(lambda: itertools_combinations(liste), number=10)
print("itertools", s)
 
#####################
# Avec beaucoup de personnes ???
#####################
 
liste = gen_liste(300, LIMIT)
print(len(liste), "personnes ...")
 
print()
s =timeit.timeit(lambda: tyrtamos(liste), number=1)
print("tyrtamos", s)
s = timeit.timeit(lambda: itertools_combinations(liste), number=1)
print("itertools", s)

[Sve@r]

300 personnes ...
Dans 2 jours un résultat ?

Ben... la ligne 300 du triangle de Pascal donne des nombres à 84 chiffres...
Les mathématiques sont impitoyables

[tbc92]

Pour 300 personnes... et les poids de ces 300 personnes, on veut atteindre une certaine somme A.
Je regarderais la somme des 300 poids : S.
2 cas de figure :
Si S > 2A, on a en principe une majorité de combinaisons dont la somme des poids va dépasser A.
Si S <= 2A, c'est l'inverse. Et dans ce cas, je vais m'intéresser à B=S-A : chercher des éléments dont la somme donne B. C'est à dire chercher les éléments qu'on doit exclure pour que la somme des autres donne A.

Je prends les 50 premières personnes. Je recense les 2^50 combinaisons possibles avec ces 50 personnes, et si certaines de ces combinaisons dépassent le nombre A, je les supprime. J'ai donc un tableau qui contient un peu moins de 2^50 lignes.
Idem avec les 50 suivantes.
J'ai donc 2 tableaux de 2^50 lignes (ou un peu moins si on a éliminé des lignes).
Je les combine. Et j'enlève les combinaisons qui dépassent A.
Et je continue avec les 50 personnes suivantes.
etc
Ca me permet d'utiliser itertools, incontournable. Mais ça me permet de limiter les volumes traités.
99.9% du travail est fait par itertools, en C. Indispensable sur des volumes comme ça.

Si A est proche de S/2, le bénéfice ne sera pas énorme (... quoique, on doit quand même diviser le temps de traitement par 10 voire plus).
Mais s'il est loin de S/2 (proche de S/5, ou 4S/5), alors c'est jackpot.

Edit :
On peut ajuster.
Je traite 90 personnes. 2^90 combinaisons, et je vire les combinaisons qui dépassent A.
Je traite 60 personnes 2^60 combinaisons. Inutile de virer les combinaisons qui dépassent A... considérant qu'il y en a peu.
Je croise ces 2 tableaux, puis je vire les combinaisons qui dépassent A.
Je traite 40 personnes , 2^40 combinaisons, je croise ce tableau avec le tableau précédent , et je vire les combinaisons qui dépassent A
Je traite 30 personnes , 2^30 combinaisons, je croise ce tableau avec le tableau précédent , et je vire les combinaisons qui dépassent A
etc avec des étapes de plus en plus petites.
L'objectif est de supprimer 'rapidement' toute combinaison qui dépasse A.

Edit 2 :
On peut calculer la somme des poids de toutes les personnes 'restantes'. Et à tout moment, virer les combinaisons qui dépassent A, mais aussi virer les combinaisons qui ont très peu de personnes : et même si dans la suite du process, on sélectionne tous les restants, on n'atteindra pas A.

Tout ça sera encore plus performant si on classe les personnes par ordre de poids décroissant. Si on met au début du process les personnes qui ont le plus gros poids, on a une plus grande visibilité, on tombe vite sur des combinaisons qui sont condamnées, soit parce qu'elles dépassent déjà A, soit parce qu'elles n'atteindront jamais A.
Edit 3 :
Parfois, on peut avoir des nombres 'non aléatoires'. Par exemple plein de nombres qui sont des multiples de 100, et quelques nombres qui ne sont pas des multiples de 100. Exemple : plein de nombres qui sont des multiples de 100, et une trentaine de nombres qui ne sont pas des multiples de 100. On regarde cette trentaine de nombres. Si le nombre A recherché finit par 54, on recense toutes les combinaisons de cette trentaine de nombres qui finissent par 54 ... et on a déjà divisé par 100 le nombre de scénarios à traiter.