Exercice de répartition d'éléments dans des groupes

Version imprimable

2 pièce(s) jointe(s)

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 :
Pièce jointe 658201
Pièce jointe 658202

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:

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

Un début de piste

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:

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:

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:

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,

14/08/2024, 14h42
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

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

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

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:

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:

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:

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

14/08/2024, 16h38
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

Je n'avais pas mis la procédure affiche_resu(), car elle ne présente pas grand intérêt...
J'ai ajouté une procédure solution_valide() qui teste si les 6 groupes ont tous 3 ou 4 éléments ;

procédures :

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
PROCÉDURE solution_valide(qscenar est un_scenar)
 
i , nn est un entier 
POUR i = 1 À 6
	nn = 0
	POUR j = 1 À 19 
		SI qscenar.tt[j] = i ALORS nn++  
	FIN
	SI nn < 3 ALORS RENVOYER Faux 
	SI nn > 4 ALORS RENVOYER Faux 
FIN
RENVOYER Vrai 
 
PROCÉDURE affiche_resu(qscenar est un_scenar,score est un réel )
 
i est un entier 
 
POUR i = 1 À 19
	Trace ( Tbval[i] , "dans le groupe n° ", qscenar.tt[i] )
FIN
POUR i = 1 À 6 
	Trace ( i, " total pour ce groupe ", qscenar.sumtt[i])
FIN
Trace ( "score total", score )

Et j'ai modifié le code du bouton 'Go', pour s'assurer que la 1ère solution vérifie la contrainte ... et ensuite pour n'enregistrer un scenario que s'il vérifie cette contrainte.
Le nouveau traitement est plus lent, parce qu'on élimine les branches pourries moins vite.

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
105
106
107
108
109
n, i , j    , jmin  , tmax  , nKkk , Kkk0  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 À 6
	jmin=i 
	Best_scenar.tt[i] = jmin 
	Best_scenar.sumtt[jmin] = Best_scenar.sumtt[jmin]  + Tbval[i]
	Best_scenar.tt[13-i] = jmin 
	Best_scenar.sumtt[jmin] = Best_scenar.sumtt[jmin]  + Tbval[13-i]
	Best_scenar.tt[i+12] = jmin 
	Best_scenar.sumtt[jmin] = Best_scenar.sumtt[jmin]  + Tbval[i+12]
FIN
POUR i = 19 À 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 ")
 
j=1
i = 1 
 
Qscenar.tt[j] = i
Qscenar.sumtt[i] = Tbval[j]
Qscenar.nB_placés = 1 
Qscenar.nMax_non_vide = 1 
TableauAjouteLigne(Tbscenar, Qscenar ) 
 
Kkk0 = 5000 
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
					// Si en plus la solution est valide (au moins 3 éléments dans chaque boite)
					SI solution_valide(newscenar ) 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
					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 ))

La solution trouvée :

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
80.3374 dans le groupe n°  1
60.54048 dans le groupe n°  2
56.94624 dans le groupe n°  3
55.3696 dans le groupe n°  2
55.13664 dans le groupe n°  4
50.752 dans le groupe n°  5
49.55808 dans le groupe n°  5
48.8072 dans le groupe n°  4
46.78128 dans le groupe n°  6
39.3354 dans le groupe n°  3
39.104 dans le groupe n°  3
38.75508 dans le groupe n°  6
37.37448 dans le groupe n°  6
34.80048 dans le groupe n°  5
31.85 dans le groupe n°  4
27.98432 dans le groupe n°  1
26.9568 dans le groupe n°  1
19.24208 dans le groupe n°  2
12.3786 dans le groupe n°  6
1  total pour ce groupe  135.27852
2  total pour ce groupe  135.15216
3  total pour ce groupe  135.38564
4  total pour ce groupe  135.79384
5  total pour ce groupe  135.11056
6  total pour ce groupe  135.28944
score total 0.68328

14/08/2024, 17h22
jurassic pork

Bon je viens d'essayer ton code tbc92, çà m'a l'air bon : on trouve le même écart max qu'en python. Chez moi le code mets 22 secondes à s'exécuter. Le code en python 6 ms. Le principal c'est que cela fonctionne et que ça ne mette pas un temps infini.
Merci à tous les deux pour votre participation.
14/08/2024, 17h41
Flodelarab

Bonjour :coucou:

J'attire quand même l'attention sur le fait que le mot "moyenne" est faux. 135/4 ne donne pas la même moyenne que 135/3. Dans l'exemple initial, le groupe 1 n'a pas une moyenne de 134,6.

De plus, je souligne que la seule façon de répartir 19 valeurs en 6 groupes avec un minimum de 3 éléments et un maximum de 4 élément est 4-3-3-3-3-3. On fait croire à une variabilité qui n'existe pas.
14/08/2024, 17h54
jurassic pork

Citation:

Envoyé par Flodelarab

Bonjour :coucou:
J'attire quand même l'attention sur le fait que le mot "moyenne" est faux. 135/4 ne donne pas la même moyenne que 135/3. Dans l'exemple initial, le groupe 1 n'a pas une moyenne de 134,6.

A noter que ce n'est pas moi qui est créé le classeur que l'on voit sur le premier message. Les noms utilisés dans les champs ne sont pas forcément bien choisis.
15/08/2024, 12h40
Flodelarab

La quantité Q des possibilités est dénombrable. On a :

$Formule mathématique$

On choisit les 4 du groupe de 4. Le premier nombre du groupe suivant est forcément le plus petit. Il faut donc en choisir 2 pour compléter le groupe. Et on recommence jusqu'à avoir 6 groupes.
194 millions de cas, on peut tous les faire, si ce n'est pas avec le tableur :D .

Citation:

le souci c'est que la permutation de 19 éléments c'est 19! = 121,645,100,408,832,000.

Euh, je n'avais pas vu, mais ton dénombrement est faux. Tu n'as pas besoin d'un ordre sur 19 éléments. {1234}{...} et {4321}{...} désigne la même solution.

Je reviendrai.
15/08/2024, 12h51
jurassic pork

Hello,

Citation:

Envoyé par Flodelarab

La quantité Q des possibilités est dénombrable. On a :

$Formule mathématique$

On choisit les 4 du groupe de 4. Le premier nombre du groupe suivant est forcément le plus petit. Il faut donc en choisir 2 pour compléter le groupe. Et on recommence jusqu'à avoir 6 groupes.
194 millions de cas, on peut tous les faire, si ce n'est pas avec le tableur :D .

Euh, je n'avais pas vu, mais ton dénombrement est faux. Tu n'as pas besoin d'un ordre sur 19 éléments. {1234}{...} et {4321}{...} désigne la même solution.

Je reviendrai.

Mon dénombrement concernait les permutations possibles sur 19 éléments :roll: . C'était dans le cas du tirage aléatoire.
Et je viens de m'apercevoir que la solution de User ne fonctionne pas à tous les coups suivant l'ordre de départ des 19 valeurs. On peut se retrouver avec un groupe de 2 valeurs à la fin (ma modif pour limiter le nombre à 3 ou 4 éléments ne fonctionne donc pas). On peut aussi avoir un écart max différent. Par contre la solution de tbc92 semble donner toujours le même résultat quelque soit l'ordre de départ des valeurs mais le temps de calcul peut devenir très très long. Avec son tri par ordre décroissant des valeurs de départ cela semble bon pour le temps de calcul.
Si tu as une autre solution à proposer n'hésite pas.

Ami calmant, J.P

Dans ma première version hier, je ne vérifiais pas si les solutions étaient du type 4+3+3+3+3+3 ; j'ai modifié pour vérifier ça.
En particulier, au début je cherche une vague solution qui va servir à établir un score de référence, pour éliminer aussi vite que possible les scénarios qui seront de toutes façons moins bons que ce score de référence.
Et dans ma 2ème version, j'ai été trop violent. Je construis une solution de référence qui vérifie la contrainte 4+3+3+3+3+3 , mais pas optimale. Et du coup, on explore les différentes branches beaucoup plus loin avant de se rendre compte qu'elles sont mauvaises.

Du coup, modification : Je construis une solution de référence, sans chichis, mais assez performante. Si elle vérifie la contrainte 4+3+3+3+3+3, c'est bon, je continue. Sinon, tant pis, je construis une autre solution de référence, qui vérifie la contrainte, mais pas très bonne.

Nouvelle version :

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
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
 
SI PAS solution_valide(Best_scenar) ALORS 
	POUR i = 1 À 6
		jmin=i 
		Best_scenar.tt[i] = jmin 
		Best_scenar.sumtt[jmin] = Best_scenar.sumtt[jmin]  + Tbval[i]
		Best_scenar.tt[13-i] = jmin 
		Best_scenar.sumtt[jmin] = Best_scenar.sumtt[jmin]  + Tbval[13-i]
		Best_scenar.tt[i+12] = jmin 
		Best_scenar.sumtt[jmin] = Best_scenar.sumtt[jmin]  + Tbval[i+12]
	FIN
	POUR i = 19 À 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
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 ")
 
j=1
i = 1 
 
Qscenar.tt[j] = i
Qscenar.sumtt[i] = Tbval[j]
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
					// Si en plus la solution est valide (au moins 3 éléments dans chaque boite)
					SI solution_valide(newscenar ) 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
					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 ))

Bonjour,

Désolé, j'avais pas vu que c'était remonté..

Concernant Python, au cours de la procédure, il faudrait en plus que le nombre de valeurs restantes vérifie toujours le test :

(nb_valeurs_restante >= nb_groupes_restant*min_elem) and (nb_valeurs_restante <= nb_groupes_restant*max_elem).

donc si l'écart entre min_elem et max_elem est petit ça va restreindre le résultat..

J'ai essayé ceci mais j'avoue que ça complique pas mal (pas testé sur plus de valeurs) :?:

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
def test_subset(nb_elem, nb_valeurs, min_elem, max_elem, nb_groupes_restant):
 
    return ((nb_valeurs-nb_elem) >= (nb_groupes_restant*min_elem)) and ((nb_valeurs-nb_elem) <= (nb_groupes_restant*max_elem))
 
 
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)
 
minElem = 3
maxElem = 4
 
# 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):
                if (len(subset)>=minElem) and (len(subset)<=maxElem) and test_subset(len(subset),len(nombres),minElem ,maxElem,(nb_groupes-i-1)):
                    # 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)
 
lens_groupes = [len(g) for g in groupes]
 
print(lens_groupes)
 
ecart_max = max(sums_groupes) - min(sums_groupes)
 
print("ecart max. = " + str(ecart_max))

Cdlt,

Hello,

Citation:

Envoyé par tbc92

Dans ma première version hier, je ne vérifiais pas si les solutions étaient du type 4+3+3+3+3+3 ; j'ai modifié pour vérifier ça.
En particulier, au début je cherche une vague solution qui va servir à établir un score de référence, pour éliminer aussi vite que possible les scénarios qui seront de toutes façons moins bons que ce score de référence.
Et dans ma 2ème version, j'ai été trop violent. Je construis une solution de référence qui vérifie la contrainte 4+3+3+3+3+3 , mais pas optimale. Et du coup, on explore les différentes branches beaucoup plus loin avant de se rendre compte qu'elles sont mauvaises.

Du coup, modification : Je construis une solution de référence, sans chichis, mais assez performante. Si elle vérifie la contrainte 4+3+3+3+3+3, c'est bon, je continue. Sinon, tant pis, je construis une autre solution de référence, qui vérifie la contrainte, mais pas très bonne.

merci de passer du temps à améliorer le code. Il y a une partie que je ne comprends pas dans celui-ci :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 SI PAS solution_valide(Best_scenar) ALORS POUR i = 1 À 6 jmin=i Best_scenar.tt[i] = jmin Best_scenar.sumtt[jmin] = Best_scenar.sumtt[jmin] + Tbval[i] Best_scenar.tt[13-i] = jmin Best_scenar.sumtt[jmin] = Best_scenar.sumtt[jmin] + Tbval[13-i] Best_scenar.tt[i+12] = jmin Best_scenar.sumtt[jmin] = Best_scenar.sumtt[jmin] + Tbval[i+12] FIN POUR i = 19 À 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 FIN
avec ceci :

Code:

Best_scenar.sumtt[jmin] = Best_scenar.sumtt[jmin] + Tbval[i]

on va se retrouver avec des valeurs qui ne sont plus bonnes car Best_scenar.sumtt[jmin] n'est pas nul au départ.
et pourquoi un :

Code:

POUR i = 19 À 19

Ami calmant, J.P

Hello,

Citation:

Envoyé par User

Merci de passer du temps et pour ton nouveau code.
J'ai fait différents essais avec et en particulier d'ordonner les valeurs de départ puis de faire des boucles où chaque fois je mélange les données de départ :

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
105
106
107
import random
def test_subset(nb_elem, nb_valeurs, min_elem, max_elem, nb_groupes_restant):
 
    return ((nb_valeurs-nb_elem) >= (nb_groupes_restant*min_elem)) and ((nb_valeurs-nb_elem) <= (nb_groupes_restant*max_elem))
 
 
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]
values.sort() 
# nombre de groupes
nb_groupes = 6
ecart = 0.0
 
somme_groupe = sum(values)/nb_groupes
 
print(somme_groupe)
 
minElem = 3
maxElem = 4
random.seed()
ecartMaximum = 9999
for i in range(5):
# 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):
                    if (len(subset)>=minElem) and (len(subset)<=maxElem) and test_subset(len(subset),len(nombres),minElem ,maxElem,(nb_groupes-i-1)):
                        # 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)
 
    lens_groupes = [len(g) for g in groupes]
 
    #print(lens_groupes)
 
    ecart_max = max(sums_groupes) - min(sums_groupes)
    print("ecart max. = " + str(ecart_max))
    print(sums_groupes)
    print(groupes)
    print(lens_groupes)
    ecartMaximum = ecart_max
    random.shuffle(values)

ce que je constate c'est que c'est le premier résultat est le meilleur et qu'ensuite c'est moins bon quelque soit le nombre de boucles que je mette. En modifiant le test de l'écart avec autre chose que 10 cela change aussi les résultats.
Je suis parti sur une autre piste qui consiste à calculer les combinaisons de 3 et 4 éléments des valeurs de départ en indiquant pour chaque somme des valeurs les indices des valeurs qui composent cette somme puis en ordonnant la liste créée. On peut limiter ainsi les combinaisons intéressantes :

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 random
from itertools import combinations
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]
values.sort() 
 combin3 = combinations(values,3)
 combrng3 = list(combinations(range(len(values)), 3)) 
 combin4 = combinations(values,4)
 combrng4 = list(combinations(range(len(values)), 4)) 
 comb3 = []
 comb4 = []
 i=0
for comb in combin3:
     comb3.append((sum(comb),combrng3[i]))
     i +=1
 i=0
for comb in combin4:
    comb4.append((sum(comb),combrng4[i]))
    i +=1
comb3.sort()
 comb4.sort()
comb = comb3[400:750]

et là je bloque : comment constituer des groupes qui n'ont pas de valeurs communes. (avec des sets isdisjoint sur les 2ème tuples ? )
Ami calmant, J.P

Citation:

Envoyé par jurassic pork

Hello,

Merci de passer du temps et pour ton nouveau code.
J'ai fait différents essais avec et en particulier d'ordonner les valeurs de départ puis de faire des boucles où chaque fois je mélange les données de départ :

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
105
106
107
import random
def test_subset(nb_elem, nb_valeurs, min_elem, max_elem, nb_groupes_restant):
 
    return ((nb_valeurs-nb_elem) >= (nb_groupes_restant*min_elem)) and ((nb_valeurs-nb_elem) <= (nb_groupes_restant*max_elem))
 
 
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]
values.sort() 
# nombre de groupes
nb_groupes = 6
ecart = 0.0
 
somme_groupe = sum(values)/nb_groupes
 
print(somme_groupe)
 
minElem = 3
maxElem = 4
random.seed()
ecartMaximum = 9999
for i in range(5):
# 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):
                    if (len(subset)>=minElem) and (len(subset)<=maxElem) and test_subset(len(subset),len(nombres),minElem ,maxElem,(nb_groupes-i-1)):
                        # 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)
 
    lens_groupes = [len(g) for g in groupes]
 
    #print(lens_groupes)
 
    ecart_max = max(sums_groupes) - min(sums_groupes)
    print("ecart max. = " + str(ecart_max))
    print(sums_groupes)
    print(groupes)
    print(lens_groupes)
    ecartMaximum = ecart_max
    random.shuffle(values)

C'est une bonne idée, tu as juste oublié de mettre à 0 l'écart au début de chaque passage de boucle :

Code:

1
2
3
4
5
6
7
8
9
10
11
#...
for i in range(5):
# parcours des écarts : 0.0, 0.1, 0.2, ..., 10
 
    ecart = 0
 
    while ecart<=10:
        # initialisation
        nombres = values[:]
        groupes = []
#...

Cdlt,

Citation:

Envoyé par User

C'est une bonne idée, tu as juste oublié de mettre à 0 l'écart au début de chaque passage de boucle :

Effectivement cela marche beaucoup mieux :
Avec ce code :

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
ecartMaximum = 9999
for n in range(5000):
    ecart = 0.0
# 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):
                    if (len(subset)>=minElem) and (len(subset)<=maxElem) and test_subset(len(subset),len(nombres),minElem ,maxElem,(nb_groupes-i-1)):
                        # 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)
 
    lens_groupes = [len(g) for g in groupes]
 
    #print(lens_groupes)
 
    ecart_max = max(sums_groupes) - min(sums_groupes)
    if ecart_max < ecartMaximum:
        print("n : " + str(n) + " -> ecart max. = " + str(ecart_max))
        #print(sums_groupes)
        #print(groupes)
        #print(lens_groupes)
        ecartMaximum = ecart_max
    random.shuffle(values)

j'obtiens rapidement ce qui semble la meilleure solution ( c'est la solution que l'on trouve avec la méthode de tbc92) :

Citation:

135.33502666666666
n : 0 -> ecart max. = 0.7571199999999862
n : 15 -> ecart max. = 0.6993999999999971
n : 19 -> ecart max. = 0.6832799999999963

J'ai beau augmenté le nombre de boucles je ne trouve pas mieux que ecart max = 0.6832799999999963. Un nombre de boucle < 100 semble suffisant.

16/08/2024, 09h51
tbc92

Citation:

on va se retrouver avec des valeurs qui ne sont plus bonnes car Best_scenar.sumtt[jmin] n'est pas nul au départ.

Oui, bien vu.
En fait, je n'ai même pas lancé cette dernière version ; il manque une remise à 0.

La boucle Pour i=19 à 19 est un 'reliquat' d'un truc précédent ; (j'avais une boucle pour i = 1 A 19 ... ) J'avais besoin de séparer ça en 2 cas, j'ai fait un copier coller ; je pouvais faire i=19, et enlever la boucle.
16/08/2024, 15h46
jurassic pork

1 pièce(s) jointe(s)

Bon j'ai réussi à intégrer le code de User dans un classeur LibreOffice calc dans la partie python embarqué. Voici ce que cela donne :

Pièce jointe 658293

Le résultat est quasi instantané pour 100 itérations.
Merci à tous pour votre participation.

Ami calmant, J.P