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

[User]

Bonjour,

Concernant l'algo, il doit y avoir d'autre possibilités sans utiliser le générateur aléatoire, par exemple :

On calcule d'abord une estimation de la somme attendue par groupe :

Code Python :

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

somme_groupe = sum([values])/nb_groupes

Ensuite, on recherche les sous-ensembles de valeurs dont la somme vaut somme_groupe à plus ou moins un écart près :

Code Python :

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

1
2
if abs(sum(subset)-somme_groupe)<=ecart then
    '...

En fait on explore un arbre binaire, et on arrête la recherche sur une branche dès que la somme partielle est supérieure à somme_groupe + ecart.

Une fois le subset trouvé on enlève les nombres qui le composent de la liste values.

On répète la procédure pour (nb_groupes-1) groupes en ajoutant à chaque fois un nouveau subset (groupe).

Le dernier groupe étant formé des nombres restant dans values.

Le souci, c'est qu'il peut y avoir des séries de valeurs pour lesquels ça peut durer..

J'ai écrit ce code Python pour le tester :

Code Python :

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
def gen_subsets(sous_ensembles, element,somme_groupe):
    # 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)<=somme_groupe:
            yield new_subset
 
 
def generateur_subsets(elements,somme_groupe):
    # 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, somme_groupe)
 
    # renvoie la générateur permettant de parcourir les sous-ensembles obtenus
    return sous_ensembles
 
 
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]
 
# nombre de groupes
nb_groupes = 6
 
ecart = 0.0
 
somme_groupe = sum(values)/nb_groupes
 
print(somme_groupe)
 
# parcours des écarts : 0.0, 0.1, 0.2, ..., 10
while ecart<=10:
    # initialisation
    nombres = values[:]
    groupes = []
 
    # parcours des groupes : 0, 1, ..., k-2
    for i in range(nb_groupes-1):
 
        # parcours des sous-ensembles
        for subset in generateur_subsets(nombres, somme_groupe+ecart):
 
            # si la somme des entiers du sous-ensemble subset est égale somme_groupe plus ou moins l'écart
            if (abs(sum(subset)-somme_groupe)<=ecart):
               # ajout du sous-ensemble de nombres
                groupes.append(subset)
                for v in subset:
                    nombres.remove(v)
                break
 
        # si pas de subset de trouvé
        if len(groupes)==i:
            break # sortie de la boucle
 
    # si groupes formés        
    if len(groupes)>i:
         break # sortie de la boucle
 
    ecart=ecart + 0.1 # incrémentation de l'écart pour une recherche
 
groupes.append(tuple(nombres)) # ajout du dernier groupe dans la liste
 
print(groupes)
 
sums_groupes = [sum(g) for g in groupes]
 
print(sums_groupes)
 
ecart_max = max(sums_groupes) - min(sums_groupes)
 
print("ecart max. = " + str(ecart_max))

Je me suis fixé comme limite un écart maxi. de 10 par rapport à la somme des valeurs attendue par groupe.

Il doit y avoir d'autres possibilités mais j'en connais pas plus, les experts du forum algo pourront t'en dire plus.

Cdlt,

[jurassic pork]

merci beaucoup User, il m'a l'air sacrément efficace ton algoritme ! je fais faire quelques tests complémentaires pour voir si cela fonctionne avec d'autres paramètres et je mettrai la discussion en résolu.
Ami calmant, J.P

[jurassic pork]

oops j'avais oublié de préciser une chose c'est qu'il faut un minimum d'éléments dans un groupe ( dans l'exemple 3) et un maximum d'éléments ( 4)
[EDIT] bon je crois que j'ai trouvé une solution :

Code python :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
minElem = 3
maxElem = 4
# ......
        for subset in generateur_subsets(nombres, somme_groupe+ecart):
 
            # si la somme des entiers du sous-ensemble subset est égale somme_groupe plus ou moins l écart
            if (abs(sum(subset)-somme_groupe)<=ecart):
                # test pour savoir si il y au moins minElem dans le subset et au plus maxElem
                if len(subset) >=  minElem and len(subset) <= maxElem:
               # ajout du sous-ensemble de nombres
                     groupes.append(subset)
                    for v in subset:
                        nombres.remove(v)
                    break

[tbc92]

Zut ... je n'ai pas appliqué la nouvelle contrainte (tous les groupes doivent contenir au moins 3 éléments) ; on doit pouvoir ajouter le test en question, sans que ça change vraiment la performance. La solution donnée par la version actuelle ne respecte pas cette contrainte.

J'ai fait ça en Windev, je sais que tu connais. Evidemment, ce n'est pas très performant, mais c'est un choix. En 38secondes, j'explore TOUTES les possibilités (en excluant celles qui vont amener à des solutions peu performantes).

Déclaratives globales :

Code :

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

1
2
3
4
5
6
7
8
 
un_scenar est une Structure 
	tt est un tableau de 19 entiers sans signe sur 1 octet
	sumtt est un tableau de 6 réels
	nB_placés  est un entier 
	nMax_non_vide est un entier 
FIN
Tbval est un tableau de 19 réels

Procédures :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
PROCÉDURE calcule_score(qscenar est un_scenar)
 
Smin, Smax est un réel 
i est un entier 
Smin = 9999999999
Smax = 0
 
POUR i = 1 À 6 
	SI qscenar.sumtt[i] < Smin ALORS Smin =  qscenar.sumtt[i]
	SI qscenar.sumtt[i] > Smax ALORS Smax =  qscenar.sumtt[i]
FIN
RENVOYER Smax - Smin

Code du bouton 'Go' :

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
n, i , j    , jmin  , tmax  est un entier
sum_min , Sum19  , Moy6 , Plafond  est un réel 
Best_scenar est un_scenar
Qscenar , newscenar , zzscenar  est un_scenar 
Tbscenar est un tableau de un_scenar 
qscore , best_score est un réel 
pb est un booléen
ch est une chaîne
dh1 , dh2  est une DateHeure 
 
ch = "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 TOUTE CHAÎNE sCh DE ch SEPAREE PAR ","
	i = i+1 
	Tbval[i]=Val(sCh) 
	Sum19 = Sum19 + Tbval[i]  	
FIN
Moy6 = Sum19 / 6 
Trace ( " la somme ideale pour chaque groupe est de " , Moy6 )
 
TableauTrie(Tbval,ttDécroissant)  // pas obligatoire, mais ça aide à faire en sorte que dès la première solution cherchée, on tombe sur une solution performante.
POUR i = 1 À 19
	Trace(Tbval[i])
FIN
 
dh1 = DateHeureSys()
POUR i = 1 À 19
	sum_min = 999999999	
	POUR j = 1 À 6 
		SI Best_scenar.sumtt[j] < sum_min ALORS 
			jmin = j 
			sum_min = Best_scenar.sumtt[j]
		FIN
	FIN
	Best_scenar.tt[i] = jmin 
	Best_scenar.sumtt[jmin] = Best_scenar.sumtt[jmin]  + Tbval[i]
FIN
best_score = calcule_score ( Best_scenar )  
Trace ( " A ce niveau, on a une valeur  de référence")
affiche_resu ( Best_scenar, best_score )
Plafond =  Moy6 + 5 * best_score / 6 
Trace ( " On peut chercher d'autres solutions, mais dès qu'un des 6 groupes va dépasser " , Plafond, " cette solution ne peut être meilleure que la solution actuelle ")
 
Qscenar.tt[1] = 1
Qscenar.sumtt[1] = Tbval[1]
Qscenar.nB_placés = 1 
Qscenar.nMax_non_vide = 1 
TableauAjouteLigne(Tbscenar, Qscenar ) 
 
TANTQUE TableauOccurrence(Tbscenar) > 0 
	n = TableauOccurrence(Tbscenar)
	Qscenar = Tbscenar[n]
	TableauSupprime(Tbscenar, n )
	tmax = Qscenar.nMax_non_vide+1
	SI tmax > 6 ALORS tmax = 6 
	POUR j = 1 À tmax 
		newscenar = Qscenar
		newscenar.tt[Qscenar.nB_placés+1] = j
		newscenar.sumtt[j] = newscenar.sumtt[j] +Tbval[ Qscenar.nB_placés+1 ]
		SI newscenar.sumtt[j] < Plafond ALORS 
			newscenar.nB_placés = Qscenar.nB_placés+1
			SI j >  newscenar.nMax_non_vide ALORS newscenar.nMax_non_vide = j 
 
			SI newscenar.nB_placés < 19 ALORS 
				TableauAjouteLigne( Tbscenar, newscenar ) 
			SINON
				qscore = calcule_score (  newscenar )  
				SI qscore < best_score ALORS 
					best_score = qscore 
					Best_scenar = newscenar
					Plafond =  Moy6 + 5 * best_score / 6 
					// Je vire tous les scénarios en attente qui ne sont plus compétitifs 
					POUR ii = TableauOccurrence(Tbscenar) À 1 PAS - 1 
						zzscenar = Tbscenar[ii]						
						pb = Faux 
						POUR jj = 1 À 6 
							SI zzscenar.sumtt[jj] > Plafond ALORS pb = Vrai 
						FIN
						SI pb ALORS 
							//trace ( " suppression scenar n°" , ii )
							TableauSupprime(Tbscenar, ii  )
						FIN
					FIN
					//info( " ok   on a amélioré ")
				FIN
			FIN
		FIN
	FIN
FIN
dh2 = DateHeureSys() 
Trace ( " Résultat final " )
affiche_resu ( Best_scenar, best_score )
Info ( " fini" , DateHeureDifférence( dh1, dh2 ))

[jurassic pork]

Merci bien Tbc92, j'ai toujours un windev 16 sous le coude, je vais essayer ton code. Tu as oublié de mettre la procédure affiche_résu