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
| import time
from itertools import permutations
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 = 1000000
Ngpe = 6
ecartMax = float('inf')
t = values
sumGrpSol = [0]*Ngpe
#perm_iterator = permutations(t, len(t))
#for it in perm_iterator:
# print(it)
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)
max = 0
min = float('inf')
sumGrp = [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]
for i in range(0,len(sumGrp)):
if sumGrp[i] < min: min = sumGrp[i]
if sumGrp[i] > max: max = sumGrp[i]
ecart = max - min
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()
end = time.time()
print('temps écoulé : ' + str(end - start) + " s")
print(tres)
print(ecartMax)
print(sumGrpSol) |