Combinaison de chiffres qui donne une valeur

Version imprimable

10/05/2024, 15h49
Jobson01

Combinaison de chiffres qui donne une valeur

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 !
10/05/2024, 16h50
fred1599

Bonjour,

Montrez au moins un début de code avec un de vos essais...
11/05/2024, 09h21
MPython Alaplancha

Bonjour.
Tu pourrais te servir de la fonction combinations du module itertools ...
11/05/2024, 13h23
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.

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:

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:

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:

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!

12/05/2024, 14h59
User

Une piste pour optimiser le code

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,
12/05/2024, 15h02
Sve@r

Citation:

Envoyé par tyrtamos

...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.

Bonjour

@Sve@r

Tu as raison! j'ai écrit "à droite" dans le texte, mais j'ai utilisé .zfill(10) dans mon code, qui a bien complété par des "0" à gauche. Ce qui fait que j'ai obtenu un comptage correct de 1 ("0b0000000001") à 1023 ("0b1111111111").

@User

Chercher une solution pour diminuer les calculs est une bonne idée, car je me suis contenté de faire ça par "force brute". En refaisant les calculs avec la liste issue du dictionnaire mais ordonnée selon les valeurs, voilà ce que je trouve dans l'ordre de comptage normal:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Trouvé ! 34 0000100010 5000 [('Bob', 2000), ('Hermann2', 3000)] Trouvé ! 36 0000100100 5000 [('Bob', 2000), ('Valérie', 3000)] Trouvé ! 40 0000101000 5000 [('Bob', 2000), ('Hermann', 3000)] Trouvé ! 66 0001000010 5000 [('Raoul', 2000), ('Hermann2', 3000)] Trouvé ! 68 0001000100 5000 [('Raoul', 2000), ('Valérie', 3000)] Trouvé ! 72 0001001000 5000 [('Raoul', 2000), ('Hermann', 3000)] Trouvé ! 257 0100000001 5000 [('Paul', 1000), ('Ben', 4000)] Trouvé ! 352 0101100000 5000 [('Paul', 1000), ('Raoul', 2000), ('Bob', 2000)] Trouvé ! 400 0110010000 5000 [('Paul', 1000), ('Victor', 1500), ('Michel', 2500)] Trouvé ! 560 1000110000 5000 [('Raoul2', 500), ('Bob', 2000), ('Michel', 2500)] Trouvé ! 592 1001010000 5000 [('Raoul2', 500), ('Raoul', 2000), ('Michel', 2500)] Trouvé ! 642 1010000010 5000 [('Raoul2', 500), ('Victor', 1500), ('Hermann2', 3000)] Trouvé ! 644 1010000100 5000 [('Raoul2', 500), ('Victor', 1500), ('Valérie', 3000)] Trouvé ! 648 1010001000 5000 [('Raoul2', 500), ('Victor', 1500), ('Hermann', 3000)] Trouvé ! 928 1110100000 5000 [('Raoul2', 500), ('Paul', 1000), ('Victor', 1500), ('Bob', 2000)] Trouvé ! 960 1111000000 5000 [('Raoul2', 500), ('Paul', 1000), ('Victor', 1500), ('Raoul', 2000)]
je constate effectivement que la dernière combinaison trouvée correspond à ce que tu proposes.

Donc, si la somme des 4 premiers correspond aux 5000 cherchés, il faudrait s'arrêter à 0b1111000000, c'est à dire 960.

Cependant, je ne sais pas si c'est dû aux valeurs prises ici, et si ça a un caractère général. Je laisse la suite au PO!

En tout cas, merci!

13/05/2024, 09h56
papajoker
bonjour

puisque le dictionnaire est donné à titre d'exemple

1) En premier lieu, je supprimerais les valeurs >= 5000 ("=" puisque ne désire qu'une somme ? donc plus d'une personne ?)

2) Si nous avons beaucoup beaucoup plus de "personnes" que de valeurs ?
N'est-il pas plus efficace de transformer le dico de départ en valeur=>personnes ???
Code:

1 2 3 4 5 6 valeurs = { 100: [pierre, paul, raoul, bibi, mama, papa, jean, ...], 1000: [ marie, loic, philippe, patrick ] .... 4000: [pierrette, paulette, jeanette, ...] }
Puis de retrouver les clés de ce dico qui ont une somme égale à 5000

reste à écrire l'algo et comparer, à partir de quelle (grande) différence cette technique est meilleure (si meilleure).

EDIT: l'utilisation du module itertools ? je pense que c'est une mauvaise idée puisque le demandeur est débutant, il faut coder par soit même !
13/05/2024, 10h02
User

@ Tyrtamos,

Merci, oui en effet c'est une possibilité. On peux aussi voir les codes binaires comme les résultats ou codes des différents parcours sur un arbre binaire (résultats en bas sur les feuilles de l'arbre) :

Durant chaque parcours des montants triés, en descendant les différents niveaux de l'arbre (gauche : 0, droite: 1 (montant retenu)), on fait la somme partielle à chaque noeud, et si elle est supérieure ou égale à 5000 on s'arrête.

mais bien sûr c'est utile surtout quand il y a beaucoup de combinaisons à générer et sous certaines conditions, sinon les codes proposés vont très bien ;)

Cdlt,
13/05/2024, 18h56
Sve@r
Citation:

Envoyé par tyrtamos

Chercher une solution pour diminuer les calculs est une bonne idée

Bizarrement je ne trouve pas. En fait, avec Python, je pense que ce serait une "fausse" bonne idée.
Si on n'avait pas le itertools.combinations alors oui là ça vaudrait le coup.
Mais là on a déjà l'algo tout écrit (et probablement écrit en C) donc inutile de se le refarcir.

Parce que sinon si on veut appliquer la méthode "tri + arrêt" il faut alors réécrire son propre algo "combinations" pour pouvoir lui dire "arrête-toi".

En résumé on a le choix entre
- un algo déjà écrit mais qui (malheureusement) sort tout y compris les inutiles (les cas qui dépassent 5000). Tant pis, on rajoute ensuite un filtre pour ne garder que les 5000 et c'est bon
- un algo dit "optimisé" qui s'arrêtera dès qu'il a une certitude perdante mais qu'on doit alors écrire
Je pense que la première solution sera plus simple à mettre en oeuvre et ne sera pas forcément beaucoup plus longue.

Citation:

Envoyé par Sve@r

...
Je pense que la première solution sera plus simple à mettre en oeuvre et ne sera pas forcément beaucoup plus longue.

Oui moi aussi, mais ça peut-être intéressant d'explorer d'autres pistes..

J'ai fait un test au niveau temps d'exécution sur une liste d'entiers positifs et négatifs (tapez un peu au hasard) et le but est de chercher les sommes nulles :

ça semble devenir intéressant à partir de 28-30 entiers :

Code:

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
import itertools
import time
 
def gen_subsets(sous_ensembles, element):
    # fonction permettant de générer les nouveaux sous-ensembles après ajout de l'élément
 
    # parcours des sous-ensembles (subset)
    for subset in sous_ensembles:
 
        # ordre de renvoyer le sous-ensemble : descente à gauche dans l'arbre binaire
        yield subset
 
        # création du nouveau sous-ensemble avec ajout du nouvel élément
        new_subset = tuple(subset) + (element,)
 
        # ordre de renvoyer le nouveau sous-ensemble  : descente à droite dans l'arbre binaire
        if sum(new_subset)<=0:
            yield new_subset
 
        # print(new_subset)
 
 
def generateur_subsets(elements):
    # permet de génèrer les sous-ensembles à partir de l'ensemble de départ
 
    # tri des éléments de l'ensemble de départ
    elements.sort()
 
    # initialisation de la variable sous_ensembles avec un élément vide : {{}}
    sous_ensembles = iter([()])
 
    # parcours des éléments de la liste de départ
    for ei in elements:
        # on génère les nouveaux sous-ensembles après ajout de ei
        sous_ensembles = gen_subsets(sous_ensembles, ei)
 
    # renvoie la générateur permettant de parcourir les sous-ensembles obtenus
    return sous_ensembles
 
def taille_maxi_combinaison(E, s):
    E.sort()
    somme = 0; n=0
    for e in E:
        somme+=e
        if somme>s:
            return n
        n+=1
 
 
E = [-8, -9, -15, 15, -33, 36, -39, 45, 46, 60, 68, 73, 80, 92, 96, -8, -9, -15, 15, -33, 36,25,27,29,30,35,37] #, 42, 45, -9] #, -15, 15, -33, 36,25,27,29,30,35,37, 42 , 45,18,120,145,12]
 
print(len(E))
 
# heure de début
start = time.time()
 
sommes_nulles1=[]
 
# création du générateur des sous-ensembles de E
gen_subsets = generateur_subsets(E)
 
next(gen_subsets) # saute le tuple vide
 
# parcours des sous-ensembles
for subset in gen_subsets:
 
    # si la somme des entiers du sous-ensemble subset est nulle
    if sum(subset)==0:
       # ajout du sous-ensemble d'entiers à somme nulle
        sommes_nulles1.append(subset)
 
# heure de fin
end = time.time()
 
# Affiche la durée d'exécution.
print(f"Durée d'exécution : {end - start} sec.")
 
print(sommes_nulles1)
 
print(len(sommes_nulles1))
 
# heure de début
start = time.time()
 
n =  taille_maxi_combinaison(E, 0) # len(E)
 
sommes_nulles2=[]
 
for i in range(1, n+1):
 
    for subset in itertools.combinations(E,i):
        if sum(subset)==0:
            # ajout du sous-ensemble d'entiers a somme nulle
            sommes_nulles2.append(subset)
 
# heure de fin
end = time.time()
 
# Affiche la durée d'exécution.
print(f"Durée d'exécution : {end - start} sec.")
 
print(sommes_nulles2)
 
print(len(sommes_nulles2))

Mais tout ça dépend bien sûr des données, s'il y a beaucoup d'entiers négatifs par exemple ça n'apporte pas grand chose.

Après il y a aussi la programmation dynamique qui permet de savoir rapidement s'il y a une solution au problème quand il y a beaucoup de valeurs.

Cdlt,

Bonjour

En fait, il faut trouver une fonction qui, à partir de [1, 2, 3], donne: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

J'ai cherché une telle fonction dans itertools, et je ne l'ai pas trouvée.

Mais, bizarrement, en cherchant avec Google, je suis rapidement tombé sur... mon site:
https://python.jpvweb.com/python/mes...rties_ensemble

Alors, je reprends une des fonctions de la page (qui date de... 2010: ça ne nous rajeunit pas!) qui résout le problème:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

Il s'agit en fait de l'exploitation du comptage binaire que j'ai utilisé plus haut.

Application avec le dico d'origine corrigé et converti en liste:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
liste = [('Raoul2', 500), ('Paul', 1000), ('Victor', 1500), ('Raoul', 2000),
 ('Bob', 2000), ('Michel', 2500), ('Hermann', 3000), ('Valérie', 3000),
 ('Hermann2', 3000), ('Ben', 4000)]
 
pl = partiesliste(liste)
 
for elem in pl:
    s = 0
    for z in elem:
        s+=z[1]
    if s==5000:
        print(elem)

Il y a bien 1024 sous listes (avec [] qui ne nous intéresse pas)

Résultats: on retrouve bien les 16 sous-listes que j'avais déjà trouvées

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[('Raoul2', 500), ('Paul', 1000), ('Victor', 1500), ('Raoul', 2000)]
[('Raoul2', 500), ('Paul', 1000), ('Victor', 1500), ('Bob', 2000)]
[('Paul', 1000), ('Raoul', 2000), ('Bob', 2000)]
[('Paul', 1000), ('Victor', 1500), ('Michel', 2500)]
[('Raoul2', 500), ('Raoul', 2000), ('Michel', 2500)]
[('Raoul2', 500), ('Bob', 2000), ('Michel', 2500)]
[('Raoul2', 500), ('Victor', 1500), ('Hermann', 3000)]
[('Raoul', 2000), ('Hermann', 3000)]
[('Bob', 2000), ('Hermann', 3000)]
[('Raoul2', 500), ('Victor', 1500), ('Valérie', 3000)]
[('Raoul', 2000), ('Valérie', 3000)]
[('Bob', 2000), ('Valérie', 3000)]
[('Raoul2', 500), ('Victor', 1500), ('Hermann2', 3000)]
[('Raoul', 2000), ('Hermann2', 3000)]
[('Bob', 2000), ('Hermann2', 3000)]
[('Paul', 1000), ('Ben', 4000)]

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

Salut,

Citation:

Envoyé par tyrtamos

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

Une proposition,

Code:

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)

14/05/2024, 08h56
tyrtamos

Bonjour fred1599

Citation:

Envoyé par 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?
14/05/2024, 09h51
fred1599

Citation:

Envoyé par tyrtamos

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).

Citation:

Envoyé par tyrtamos

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.
14/05/2024, 10h37
jurassic pork

Hello,

Citation:

Envoyé par tyrtamos

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 :

Citation:

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

Ami calmant, J.P

@jurassic_pork,

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

Code:

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)

14/05/2024, 11h45
jurassic pork

Citation:

Envoyé par fred1599

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

voici ce que cela donne avec le backtrack :

Citation:

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

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 :aie:.

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

Code:

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 ? :roll:

Code:

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)

14/05/2024, 20h47
Sve@r

Citation:

Envoyé par papajoker

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

Ben... la ligne 300 du triangle de Pascal donne des nombres à 84 chiffres...
Les mathématiques sont impitoyables 8-)
15/05/2024, 09h43
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.

Bonjour

Merci tbc92. Tout cela me donne plein d'idées! Il faudrait féliciter le PO d'avoir posé une aussi bonne question (mais aussi lui reprocher d'être parti aussi vite...).

Je suis maintenant convaincu que l'utilisation des combinaisons du module itertools est la meilleure solution, et de loin.

J'ai dit qu'on avait besoin d'une fonction pour calculer la liste de tous les groupements possibles des éléments d'une liste. Par exemple
- à partir de: [1,2,3]
- renvoie: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Avec les combinaisons de itertools, une telle fonction, présentée ici comme générateur, devient hyper-simple:
Code:

1 2 3 4 5 6 7 8 9 10 from itertools import combinations def partiesliste(seq): """Generateur qui calcule la liste de tous les groupements possibles entre les éléments de la liste seq. ex: [1,2,3] => [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] - seq: liste à traiter. """ for i in range(0, len(seq)+1): for comb in combinations(seq, i): yield comb
Ce qui est intéressant dans cette fonction, c'est que les éléments de la liste finale sont renvoyés par niveau de groupements:
- [] en premier (qui, ici, ne nous intéresse pas)
- (1,) (2,) et (3,): les groupements de 1 élément
- (1, 2) (1, 3) et (2, 3): les groupements de 2 éléments
- (1, 2, 3): les groupements de 3 éléments (ici, il n'y en a qu'un, et c'est le dernier)
Ce qui est intéressant pour notre problème, c'est que ça va nous permettre de diminuer la quantité de calculs!

Rappelons la liste de départ: le dictionnaire de départ, après corrections et tri croissant pour les valeurs:
Code:

1 2 3 seq = [('Raoul2', 500), ('Paul', 1000), ('Victor', 1500), ('Raoul', 2000), ('Bob', 2000), ('Michel', 2500), ('Hermann', 3000), ('Valérie', 3000), ('Hermann2', 3000), ('Ben', 4000)]
On voit bien qu'on n'a pas besoin de calculer la somme cumulée avec les groupements de 1 élément, puisque l'élément maxi est inférieur à 5000. Cela aurait pu être le cas avec les groupements de 2 éléments si le cumul des valeurs des 2 éléments de plus fort poids n'atteignait pas 5000. Etc... Et voilà comment, dans le cas général, on peut calculer le 1er niveau de groupements utile qui s’appellera ici "imin":

# élimination des petits groupements
Code:

1 2 3 4 5 6 7 8 9 10 11 lg = len(seq) cumobj = 5000 imin = 0 cum = 0 # cumul des valeurs for i in range(lg-1, -1, -1): cum += seq[i][1] print(cum, i) if cum >= cumobj: imin = lg-i break print("imin:", imin)
On trouve ici imin=2

De même pour les groupements supérieurs. Comme la liste est triée, on voit que la somme des 4 premiers les plus faibles est déjà égale à 5000. Donc, en prenant des groupements de 5 éléments, on sera forcément supérieurs à 5000. Ce n'est donc pas nécessaire de les calculer.

Voilà comment on peut calculer dans le cas général le dernier niveau de groupement utile. On l’appellera ici "imax".
Code:

1 2 3 4 5 6 7 8 9 10 11 12 # élimination des grands groupements lg = len(seq) cumobj = 5000 imax = 0 cum = 0 for i in range(0, lg): cum += seq[i][1] print(cum, i) if cum > cumobj: imax = i break print("imax:", imax)
On trouvera ici imax=4

On va maintenant modifier la fonction de calcul "partiesliste(seq)" pour éviter de calculer les groupements inutiles:
Code:

1 2 3 4 5 6 7 8 9 10 11 def partiesliste2(seq, imin=0, imax=-1): """Générateur qui calcule la liste de tous les groupements possibles entre les éléments de la liste seq. ex: [1,2,3] => [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] - seq: liste à traiter. - imin: premier niveau de groupement(s) à calculer - imax= dernier niveau de groupement(s) à calculer """ imax = len(seq)-1 if imax<0 else imax for i in range(imin, imax+1): for comb in combinations(seq, i): yield comb
Faisons maintenant le calcul dans le cas à traiter ici, donc avec imin=2 et imax=4:
Code:

1 2 3 4 5 6 7 for res in partiesliste2(seq, imin, imax): cum = 0 for k in range(0, len(res)): cum += res[k][1] # Test pour afficher les groupements qui conviennent if cum==cumobj: print(cum, res)
On retrouve, bien sûr, les 16 groupements "gagnants" pour avoir une somme des valeurs égale à 5000.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 5000 (('Paul', 1000), ('Ben', 4000)) 5000 (('Raoul', 2000), ('Hermann', 3000)) 5000 (('Raoul', 2000), ('Valérie', 3000)) 5000 (('Raoul', 2000), ('Hermann2', 3000)) 5000 (('Bob', 2000), ('Hermann', 3000)) 5000 (('Bob', 2000), ('Valérie', 3000)) 5000 (('Bob', 2000), ('Hermann2', 3000)) 5000 (('Raoul2', 500), ('Victor', 1500), ('Hermann', 3000)) 5000 (('Raoul2', 500), ('Victor', 1500), ('Valérie', 3000)) 5000 (('Raoul2', 500), ('Victor', 1500), ('Hermann2', 3000)) 5000 (('Raoul2', 500), ('Raoul', 2000), ('Michel', 2500)) 5000 (('Raoul2', 500), ('Bob', 2000), ('Michel', 2500)) 5000 (('Paul', 1000), ('Victor', 1500), ('Michel', 2500)) 5000 (('Paul', 1000), ('Raoul', 2000), ('Bob', 2000)) 5000 (('Raoul2', 500), ('Paul', 1000), ('Victor', 1500), ('Raoul', 2000)) 5000 (('Raoul2', 500), ('Paul', 1000), ('Victor', 1500), ('Bob', 2000))
Voyons maintenant ce qu'on a gagné comme calculs:

- comme imin=2, on a évité de calculer tous les groupements de 1 élément, c'est à dire 10 (+ [] qui ne nous intéresse pas ici mais qui aurait fait appeler quand même combinations())

- comme imax=4, on a évité tous les groupements de 5, 6, 7, 8, 9 et 10 éléments, et là, c'est important! en comparant avec le liste complète, la dernière ligne calculée avec 4 éléments est le ligne 386: on a donc gagné les 1024-386=638 dernières lignes, et qui correspondent aux groupements les plus complexes!

Je n'ai pas fait de test de rapidité, mais c'est en tout cas ma meilleure solution. :D

Hello, je me permets de communiquer comment je procèderais en utilisant la fonction itertools évoquée plus haut.

J'ai modifié légèrement la liste pour supprimer le doublon (impossible dans un dictionnaire).
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import itertools # Dictionnaire de prénoms/valeurs dictionnaire = {"Raoul": 2000, "Hermann": 3000, "Victor": 1500, "Paul": 1000, \ "Michel": 2500, "Valérie": 3000, "Bob": 2000, "Raoul2": 500, "Ben": 4000} # Recherche des combinaisons dont la somme des valeurs est égale à 5000 def trouver_combinaisons(liste, target_sum): resultat = [] items = list(liste.items()) for r in range(1, len(items) + 1): for combinaison in itertools.combinations(items, r): if sum(valeur for _, valeur in combinaison) == target_sum: resultat.append(combinaison) return resultat # Appel de la fonction combinations = trouver_combinaisons(dictionnaire, 5000) # Afficher les résultats for combinaison in combinations: print(combinaison)
Résultat :

Citation:

(('Raoul', 2000), ('Hermann', 3000))
(('Raoul', 2000), ('Valérie', 3000))
(('Hermann', 3000), ('Bob', 2000))
(('Paul', 1000), ('Ben', 4000))
(('Valérie', 3000), ('Bob', 2000))
(('Raoul', 2000), ('Paul', 1000), ('Bob', 2000))
(('Raoul', 2000), ('Michel', 2500), ('Raoul2', 500))
(('Hermann', 3000), ('Victor', 1500), ('Raoul2', 500))
(('Victor', 1500), ('Paul', 1000), ('Michel', 2500))
(('Victor', 1500), ('Valérie', 3000), ('Raoul2', 500))
(('Michel', 2500), ('Bob', 2000), ('Raoul2', 500))
(('Raoul', 2000), ('Victor', 1500), ('Paul', 1000), ('Raoul2', 500))
(('Victor', 1500), ('Paul', 1000), ('Bob', 2000), ('Raoul2', 500))