Discussion :

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

[tyrtamos]

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 :

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

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 :

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

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 :

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

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 :

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

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 :

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

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 :

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

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 :

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

[Michelk12]

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 :

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

(('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))