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.

[tyrtamos]

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 :

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é ! 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!

[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 :

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

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 !

[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,

[Sve@r]

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.

[User]

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

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

[tyrtamos]

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 :

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

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

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 :

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
[('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!

[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?

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

[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]

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