Divisez la liste en trois listes de telle sorte que leurs sommes soient proches les unes des autres.

Question

Disons que j'ai un tableau de nombres S = [6, 2, 1, 7, 4, 3, 9, 5, 3, 1]. Je veux le diviser en trois tableaux. L'ordre des nombres et le nombre d'éléments dans ces tableaux n'ont pas d'importance.

Disons que A1, A2 et A3 sont les sous-réseaux. Je veux minimiser la fonction

f(x) = ( SUM(A1) - SUM(S) / 3 )^2 / 3 +
       ( SUM(A2) - SUM(S) / 3 )^2 / 3 +
       ( SUM(A3) - SUM(S) / 3 )^2 / 3

• Je n'ai pas besoin d'une solution optimale ; j'ai juste besoin d'une solution qui soit suffisamment bonne.
• Je ne veux pas d'un algorithme trop lent. Je peux échanger un peu de vitesse contre un meilleur résultat, mais je ne peux pas en échanger trop.
• La longueur de S est d'environ 10 à 30.

Por qué

Pourquoi dois-je résoudre ce problème ? Je veux disposer joliment la boîte en trois colonnes de telle sorte que la hauteur totale de chaque colonne ne soit pas trop différente de celle des autres.

Ce que j'ai essayé

Mon premier réflexe est d'utiliser greedy. Le résultat n'est pas si mauvais, mais il ne garantit pas une solution optimale. Existe-t-il une meilleure solution ?

s = [6, 2, 1, 7, 4, 3, 9, 5, 3, 1]
s = sorted(s, reverse=True)

a = [[], [], []]
sum_a = [0, 0, 0]

for x in s:
    i = sum_a.index(min(sum_a))
    sum_a[i] += x
    a[i].append(x)

print(a)

Answer 1

Comme vous avez dit qu'une solution non optimale ne vous dérangeait pas, j'ai pensé réutiliser votre fonction initiale et ajouter un moyen de trouver un bon arrangement de départ pour votre liste initiale. s

Votre fonction initiale :

def pigeon_hole(s):
    a = [[], [], []]
    sum_a = [0, 0, 0]
    for x in s:
        i = sum_a.index(min(sum_a))
        sum_a[i] += x
        a[i].append(x)
    return map(sum, a)

C'est un moyen de trouver un ordre initial raisonnable pour votre liste, il fonctionne en créant des rotations de votre liste dans l'ordre trié et trié inversé. La meilleure rotation est trouvée en minimisant l'écart-type, une fois que la liste a été classée :

def rotate(l):
    l = sorted(l)
    lr = l[::-1]
    rotation = [np.roll(l, i) for i in range(len(l))] + [np.roll(lr, i) for i in range(len(l))]
    blocks = [pigeon_hole(i) for i in rotation]
    return rotation[np.argmin(np.std(blocks, axis=1))]  # the best rotation

import random
print pigeon_hole(rotate([random.randint(0, 20) for i in range(20)]))

# Testing with some random numbers, these are the sums of the three sub lists
>>> [64, 63, 63]

Bien que cela puisse être optimisé davantage, c'est assez rapide : 0,0013s pour 20 numéros. Je fais une comparaison rapide avec la réponse de @Mo Tao, en utilisant la méthode suivante a = rotate(range(1, 30))

# This method
a = rotate(range(1, 30))
>>> [[29, 24, 23, 18, 17, 12, 11, 6, 5], [28, 25, 22, 19, 16, 13, 10, 7, 4, 1], [27, 26, 21, 20, 15, 14, 9, 8, 3, 2]]
map(sum, a)
# Sum's to [145, 145, 145] in 0.002s

# Mo Tao's method
>>> [[25, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1], [29, 26, 20, 19, 18, 17, 16], [28, 27, 24, 23, 22, 21]]
# Sum's to [145, 145, 145] in 1.095s

Cette méthode semble également trouver la solution optimale dans de nombreux cas, bien que cela ne soit probablement pas le cas dans tous les cas. Je teste cette mise en œuvre 500 fois en utilisant une liste de 30 nombres contre la réponse de Mo Tao, et je compare si les sous-listes donnent la même quantité :

c = 0
for i in range(500):
    r = [random.randint(1, 10) for j in range(30)]
    res = pigeon_hole(rotate(r))
    d, e = sorted(res), sorted(tao(r))  # Comparing this to the optimal solution by Mo Tao
    if all([k == kk] for k, kk in zip(d, e)):
        c += 1
    memory = {}
    best_f = pow(sum(s), 3)
    best_state = None

>>> 500 # (they do)

J'ai pensé faire une mise à jour avec une version plus optimisée de ma fonction ici :

def rotate2(l):
    # Calculate an acceptable minimum stdev of the pigeon holed list
    if sum(l) % 3 == 0:
        std = 0
    else:
        std = np.std([0, 0, 1])

    l = sorted(l, reverse=True)
    best_rotation = None
    best_std = 100

    for i in range(len(l)):
        rotation = np.roll(l, i)
        sd = np.std(pigeon_hole(rotation))

        if sd == std:  
            return rotation  # If a min stdev if found 

        elif sd < best_std:
            best_std = sd
            best_rotation = rotation

    return best_rotation

Le principal changement est que la recherche d'un bon ordonnancement s'arrête une fois qu'une rotation appropriée a été trouvée. De plus, seule la liste triée à l'envers est recherchée, ce qui ne semble pas modifier le résultat. En synchronisant cela avec

print timeit.timeit("rotate2([random.randint(1, 10) for i in range(30)])", "from __main__ import rotate2, random", number=1000) / 1000.

entraîne une augmentation importante de la vitesse. Sur mon ordinateur actuel rotate prend environ 1,84 ms et rotate2 prend environ 0.13ms, soit une accélération d'environ 14x. Pour comparaison, l'implémentation de 's a pris environ 0.99ms sur ma machine.

Answer 2

Comme je l'ai mentionné dans le commentaire de la question, il s'agit de la méthode de programmation dynamique directe. Il faut moins d'une seconde pour s = range(1, 30) et donne une solution optimisée.

Je pense que le code est auto-expliqué si vous connaissez Mémorisation .

s = range(1, 30)
# s = [6, 2, 1, 7, 4, 3, 9, 5, 3, 1]
n = len(s)

memory = {}
best_f = pow(sum(s), 3)
best_state = None

def search(state, pre_state):
    global memory, best_f, best_state    
    s1, s2, s3, i = state
    f = s1 * s1 + s2 * s2 + s3 * s3
    if state in memory or f >= best_f:
        return
    memory[state] = pre_state
    if i == n:
        best_f = f
        best_state = state
    else:
        search((s1 + s[i], s2, s3, i + 1), state)
        search((s1, s2 + s[i], s3, i + 1), state)
        search((s1, s2, s3 + s[i], i + 1), state)

search((0, 0, 0, 0), None)

a = [[], [], []]
state = best_state
while state[3] > 0:
    pre_state = memory[state]
    for j in range(3):
        if state[j] != pre_state[j]:
            a[j].append(s[pre_state[3]])
    state = pre_state

print a
print best_f, best_state, map(sum, a)

Answer 3

Nous pouvons rechercher la stabilité de la solution que vous avez trouvée en ce qui concerne le remplacement des éléments entre les listes trouvées. J'ai placé mon code ci-dessous. Si nous améliorons la fonction cible par un remplacement, nous conservons les listes trouvées et allons plus loin en espérant que nous améliorerons encore la fonction par un autre remplacement. Comme point de départ, nous pouvons prendre votre solution. Le résultat final sera quelque chose comme un minimum local.

from copy import deepcopy

s = [6, 2, 1, 7, 4, 3, 9, 5, 3, 1]
s = sorted(s, reverse=True)

a = [[], [], []]
sum_a = [0, 0, 0]

for x in s:
    i = sum_a.index(min(sum_a))
    sum_a[i] += x
    a[i].append(x)

def f(a):
    return ((sum(a[0]) - sum(s) / 3.0)**2 + (sum(a[1]) - sum(s) / 3.0)**2 + (sum(a[2]) - sum(s) / 3.0)**2) / 3

fa = f(a)

while True:
    modified = False

    # placing
    for i_from, i_to in [(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)]:
        for j in range(len(a[i_from])):
            a_new = deepcopy(a)
            a_new[i_to].append(a_new[i_from][j])
            del a_new[i_from][j]
            fa_new = f(a_new)
            if fa_new < fa:
                a = a_new
                fa = fa_new
                modified = True
                break
        if modified:
            break

    # replacing
    for i_from, i_to in [(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)]:
        for j_from in range(len(a[i_from])):
            for j_to in range(len(a[i_to])):
                a_new = deepcopy(a)
                a_new[i_to].append(a_new[i_from][j_from])
                a_new[i_from].append(a_new[i_to][j_to])
                del a_new[i_from][j_from]
                del a_new[i_to][j_to]
                fa_new = f(a_new)
                if fa_new < fa:
                    a = a_new
                    fa = fa_new
                    modified = True
                    break
            if modified:
                break
        if modified:
            break

    if not modified:
        break

print(a, f(a)) # [[9, 3, 1, 1], [7, 4, 3], [6, 5, 2]] 0.2222222222222222222

Il est intéressant de noter que cette approche fonctionne bien même si nous commençons avec des données arbitraires. a :

from copy import deepcopy

s = [6, 2, 1, 7, 4, 3, 9, 5, 3, 1]

def f(a):
    return ((sum(a[0]) - sum(s) / 3.0)**2 + (sum(a[1]) - sum(s) / 3.0)**2 + (sum(a[2]) - sum(s) / 3.0)**2) / 3

a = [s, [], []]
fa = f(a)

while True:
    modified = False

    # placing
    for i_from, i_to in [(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)]:
        for j in range(len(a[i_from])):
            a_new = deepcopy(a)
            a_new[i_to].append(a_new[i_from][j])
            del a_new[i_from][j]
            fa_new = f(a_new)
            if fa_new < fa:
                a = a_new
                fa = fa_new
                modified = True
                break
        if modified:
            break

    # replacing
    for i_from, i_to in [(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)]:
        for j_from in range(len(a[i_from])):
            for j_to in range(len(a[i_to])):
                a_new = deepcopy(a)
                a_new[i_to].append(a_new[i_from][j_from])
                a_new[i_from].append(a_new[i_to][j_to])
                del a_new[i_from][j_from]
                del a_new[i_to][j_to]
                fa_new = f(a_new)
                if fa_new < fa:
                    a = a_new
                    fa = fa_new
                    modified = True
                    break
            if modified:
                break
        if modified:
            break

    if not modified:
        break

print(a, f(a)) # [[3, 9, 2], [6, 7], [4, 3, 1, 1, 5]] 0.2222222222222222222

Il fournit un résultat différent mais la même valeur de la fonction.

Answer 4

Je dois dire que votre fonction gourmande produit de bons résultats mais a tendance à devenir très lente si la taille de l'entrée est grande, disons plus de 100.

Mais, vous avez dit que votre taille d'entrée est fixée dans l'intervalle - 10,30 . Au lieu de devenir trop gourmand au début, je propose de devenir un peu paresseux au début et de devenir gourmand à la fin.

Voici une fonction modifiée lazy :

def lazy(s):
    k = (len(s)//3-2)*3 #slice limit

    s.sort(reverse=True)
    #Perform limited extended slicing
    a = [s[1:k:3],s[2:k:3],s[:k:3]]

    sum_a = list(map(sum,a))
    for x in s[k:]:
        i = sum_a.index(min(sum_a))
        sum_a[i] += x
        a[i].append(x)
    return a

Ce qu'il fait, c'est qu'il trie d'abord l'entrée dans l'ordre décroissant et remplit les éléments dans trois sous-listes un par un jusqu'à ce qu'il reste environ 6 éléments.

Cette méthode prend très peu de temps et est en moyenne plus précise que l'approche avide.

Voici un graphique linéaire de la taille en fonction du temps -

et la taille par rapport à la précision -

La précision est l'écart type par rapport à la moyenne des sous-listes finales et de la liste originale. Parce que vous voulez que les colonnes s'empilent à une hauteur presque similaire et non à la hauteur (moyenne de la liste originale).

En outre, la valeur de l'élément se situe entre 3-15 donc cette somme est d'environ 100-150 comme vous l'avez mentionné.

Ce sont les fonctions de test -

def test_accuracy():
    rsd = lambda s:round(math.sqrt(sum([(sum(s)//3-y)**2 for y in s])/3),4)
    sm = lambda s:list(map(sum,s))

    N=[i for i in range(10,30)]
    ST=[]
    MT=[]
    for n in N:
        case = [r(3,15) for x in range(n)]

        ST.append(rsd(sm(lazy(case))))
        MT.append(rsd(sm(pigeon(case))))

    strace = go.Scatter(x=N,y=ST,name='Lazy pigeon')
    mtrace = go.Scatter(x=N,y=MT,name='Pigeon')
    data = [strace,mtrace]

    layout = go.Layout(
    title='Uniform distribution in 3 sublists',
    xaxis=dict(title='List size',),
    yaxis=dict(title='Accuracy - Standard deviation',))
    fig = go.Figure(data=data, layout=layout)

    plotly.offline.plot(fig,filename='N vs A2.html')

def test_timings():
    N=[i for i in range(10,30)]
    ST=[]
    MT=[]
    for n in N:
        case = [r(3,15) for x in range(n)]           
        start=time.clock()
        lazy(case)
        ST.append(time.clock()-start)
        start=time.clock()
        pigeon(case)
        MT.append(time.clock()-start)

    strace = go.Scatter(x=N,y=ST,name='Lazy pigeon')
    mtrace = go.Scatter(x=N,y=MT,name='Pigeon')
    data = [strace,mtrace]

    layout = go.Layout(
    title='Uniform distribution in 3 sublists',
    xaxis=dict(title='List size',),
    yaxis=dict(title='Time (seconds)',))

    fig = go.Figure(data=data, layout=layout)

    plotly.offline.plot(fig,filename='N vs T2.html')

Voici la version complète fichier .

Modifier -

J'ai testé la précision de la réponse de Kezzos et elle est très bonne. La déviation est restée inférieure à 0,8 tout le temps.

Écart-type moyen sur 100 passages.

  Lazy Pigeon     Pigeon         Rotation
  1.10668795      1.1573573      0.54776425

Dans le cas de la vitesse, l'ordre est assez élevé pour la fonction de rotation à comparer. Mais, 10^-3 est très bien, sauf si vous voulez exécuter cette fonction de façon répétée.

  Lazy Pigeon     Pigeon         Rotation
  5.384013e-05    5.930269e-05   0.004980

Voici un graphique à barres comparant la précision des trois fonctions. -

Dans l'ensemble, la solution de Kezzos est la meilleure si la vitesse vous convient.

Fichiers Html de plotly - en fonction du temps , par rapport à la précision et le diagramme en barres .

Answer 5

Voici mon implémentation farfelue de celle de Korf. 1 Sequential Number Partitioning (SNP), mais il n'utilise que Karmarkar-Karp au lieu de Complete Karmarkar-Karp pour la partition à deux voies (j'ai inclus une fonction inutilisée et peu satisfaisante de version de CKK - peut-être quelqu'un a-t-il une suggestion pour le rendre plus efficace ?). Sur le premier sous-ensemble, il place des limites inférieures et supérieures. Voir l'article référencé. Je suis sûr que des implémentations plus efficaces peuvent être faites. Modifier MAX_ITERATIONS pour de meilleurs résultats contre une attente plus longue :)

Au fait, la fonction, KK3 (extension de Karmarkar-Karp à la partition à trois voies, utilisée pour calculer la première borne inférieure), semble assez bonne en soi.

from random import randint
from collections import Counter
from bisect import insort
from time import time

def KK3(s):
  s = list(map(lambda x: (x,0,0,[],[],[x]),sorted(s)))

  while len(s) > 1:
    large = s.pop()
    small = s.pop()
    combined = sorted([large[0] + small[2], large[1] + small[1],
large[2] + small[0]],reverse=True)
    combined = list(map(lambda x: x - combined[2],combined))
    combined = combined + sorted((large[3] + small[5], large[4] +
small[4], large[5] + small[3]),key = sum)
    insort(s,tuple(combined))

  return s

#s = [6, 2, 1, 7, 4, 3, 9, 5, 3, 1]

s = [randint(0,100) for r in range(0,30)]

# global variables
s = sorted(s,reverse=True)
sum_s = sum(s)
upper_bound = sum_s // 3
lower_bound = sum(KK3(s)[0][3])
best = (sum_s,([],[],[]))
iterations = 0
MAX_ITERATIONS = 10000

def partition(i, accum):
  global lower_bound, best, iterations
  sum_accum = sum(accum)

  if sum_accum > upper_bound or iterations > MAX_ITERATIONS:
    return

  iterations = iterations + 1

  if sum_accum >= lower_bound:
    rest = KK(diff(s,accum))[0]
    new_diff = sum(rest[1]) - sum_accum

    if new_diff < best[0]:
      best = (new_diff,(accum,rest[1],rest[2]))
      lower_bound = (sum_s - 2 * new_diff) // 3
      print("lower_bound: " + str(lower_bound))

  if not best[0] in [0,1] and i < len(s) - 1 and sum(accum) + sum(s[i
+ 1:]) > lower_bound:
    _accum = accum[:]
    partition(i + 1, _accum + [s[i]])
    partition(i + 1, accum)

def diff(l1,l2):
  return list((Counter(l1) - Counter(l2)).elements())

def KK(s):
  s = list(map(lambda x: (x,[x],[]),sorted(s)))

  while len(s) > 1:
    large = s.pop()
    small = s.pop()
    insort(s,(large[0] - small[0],large[1] + small[2],large[2] + small[1]))

  return s

print(s)
start_time = time()
partition(0,[])
print(best)
print("iterations: " + str(iterations))
print("--- %s seconds ---" % (time() - start_time))

1 Richard E. Korf, Multi-Way Number Partitioning, Computer Science Department, University of California, Los Angeles ; aaai.org/ocs/index.php/IJCAI/IJCAI-09/paper/viewFile/625/705