Discussion :

[jurassic pork]

Hello,
voici un problème que j'ai posé dans le forum python de developpez mais pour l'instant je n'ai pas eu de réponse probante :
A partir d'une liste de flottants, regrouper les flottants par groupes de telle façon que la somme des flottants de chaque groupe ait un écart minimal avec les autres groupes. Le nombre de groupes est fixe.
Exemple : il y a 19 valeurs de départ qui doivent être "dispatchées" en 6 groupes.

Code :

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

1 2	values = [56.94624,39.104,27.98432,26.9568,60.54048,48.8072,49.55808,31.85,50.752,55.3696, 46.78128,34.80048,38.75508,55.13664,39.3354,37.37448,80.3374,19.24208,12.3786]

Pour bien voir ce que l'on cherche voici une visualisation dans un classeur Excel :



La seule solution que j'ai trouvé pour l'instant c'est de faire un mélange aléatoire des valeurs de départs et de faire beaucoup d'itérations Les valeurs de départ sont affectées arbitrairement suivant leur indice à un groupe ( 5 groupes de 3 éléments et 1 groupe de 4 éléments).
Voici mon code en python :

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
import time
import random
 
start = time.time()
values = [56.94624,39.104,27.98432,26.9568,60.54048,48.8072,49.55808,31.85,50.752,55.3696,
          46.78128,34.80048,38.75508,55.13664,39.3354,37.37448,80.3374,19.24208,12.3786]
random.seed()
nbfois = 10000000
Ngpe = 6
ecartMax = float('inf')
t = values
sumGrpSol = [0]*Ngpe
grp = [0]*len(t)
# calcul du nombre d éléments minimum par groupe
NparGpeMin = len(t) // Ngpe
# création de la liste des groupes
for i in range(0,(Ngpe * NparGpeMin)+1):
    grp[i] = 1 + (i  // NparGpeMin)
for i in range((Ngpe * NparGpeMin),len(t)):
    grp[i] = i - (Ngpe* NparGpeMin) + 1
for nbf in range(nbfois,-1,-1):
    #print(grp)
    # mélange des valeurs
    random.shuffle(t)
    maxi = 0
    mini = float('inf')
    sumGrp = [0]*Ngpe
    sumGrpt = (0,)*Ngpe
    # calcul de la somme des éléments pour chaque groupe
    for i in range(0,len(t)):
        sumGrp[grp[i] -1] =  sumGrp[grp[i] -1] + t[i]
    ecart = max(sumGrp) - min(sumGrp)
    if ecart < ecartMax:
        ecartMax = ecart
        tres = []
        #Mémorisation sous forme de tuple
        for i in range(0,len(t)):
            tres.append((t[i],grp[i]))
            sumGrpSol = sumGrp.copy()
    if nbf%1000000 == 0:
        print(tres)
        print(ecartMax)
        print(sumGrpSol)
end = time.time()  
print('temps écoulé : ' + str(end - start) + " s")

Dans cet exemple je fais 10000000 d'itérations et j'affiche le résultat tous les 1000000 d'itérations. Avec cette méthode je ne suis pas certain de trouver la solution optimale et cela mets 10 secondes pour 1000000 d'itérations.
J'ai essayé des fonctions combinatoires python mais le souci c'est que la permutation de 19 éléments c'est 19! = 121,645,100,408,832,000. Balayer tout cela c'est énormément de temps.
Peut-être faut-il utiliser des fonctions de probabilité ou de statistiques (je ne connais pas ces domaines) pour réduire le temps de calcul ou bien simplifier la recherche.
Ami calmant, J.P