Discussion :

[jurassic pork]

hello,
voici un petit exercice de répartition qui a été résolu en VBA, à voir si c'est "facilement faisable" en python.
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]

Voici une solution trouvée par le VBA avec une itération de 1000000 (trouvée en 8 secondes).





Sachant qu'en relançant le calcul dans la solution VBA on a pas tout à fait toujours le même résultat (même valeur moyenne par groupe mais Ecart Max différent). Et cela varie aussi avec le nombre d'itérations choisi.

Ami calmant, J.P

[jurassic pork]

Hello,
puisque personne n'a l'air de proposer quelque chose, j'ai essayé de traduire le code VBA en brut de fonderie python. Voici à ce que je suis arrivé (sans chercher à optimiser) :

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

Cela a l'air de donner un résultat cohérent :

temps écoulé : 9.891370058059692 s
[(34.80048, 1), (46.78128, 1), (12.3786, 1), (56.94624, 2), (38.75508, 2), (39.3354, 2), (55.13664, 3), (31.85, 3), (49.55808, 3), (26.9568, 4), (80.3374, 4), (27.98432, 4), (55.3696, 5), (19.24208, 5), (60.54048, 5), (37.37448, 6), (48.8072, 6), (50.752, 6), (39.104, 1)]
3.8693199999999877
[133.06436000000002, 135.03672, 136.54471999999998, 135.27852000000001, 135.15216, 136.93368]

Le principe est simple : on affecte à chaque élément de la liste des valeurs, un numéro de groupe puis on mélange les valeurs en regardant si à chaque itération on a un meilleur résultat. Plus
on a d'itérations plus on a de chance de trouver une meilleure solution. J'ai essayé de regarder pour balayer toutes les permutations possibles mais on arrive à 121645100408832000 cas possibles.
Pour l'instant ce code est moins rapide que le code VBA (10 s contre 7s en VBA) Les pistes possible d'optimisation : le calcul parallèle par cores. L'utilisation de np. L'utilisation d'expressions lambdas et sûrement d'autres astuces.
Ami calmant, J.P

[wiztricks]

Les pistes possible d'optimisation : le calcul parallèle par cores. L'utilisation de np. L'utilisation d'expressions lambdas et sûrement d'autres astuces.

Quelque soit le langage, la première piste sera de revoir l'algo.

- W