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

[tbc92]

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 :

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

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

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

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

[Flodelarab]

Bonjour

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.

[jurassic pork]

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

[Flodelarab]

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



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 .

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.

[jurassic pork]

Hello,

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



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 .

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

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

Nouvelle version :

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

[User]

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

[jurassic pork]

Hello,

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 :

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

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

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 :

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

POUR i = 19 À 19

Ami calmant, J.P

[jurassic pork]

Hello,

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

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

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

[User]

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

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

Code Python :

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

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,

[jurassic pork]

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

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.

[tbc92]

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.

[jurassic pork]

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 :



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

Ami calmant, J.P