Разделите список на три списка, чтобы их сумма была близка друг к другу

Ответ 1

Как вы сказали, вы не возражаете против неоптимального решения, хотя я бы снова использовал вашу начальную функцию и добавил способ найти хорошую стартовую схему для вашего первоначального списка s

Ваша начальная функция:

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)

Это способ поиска разумного первоначального заказа для вашего списка, он работает, создавая вращения вашего списка в отсортированном и обратном порядке сортировки. Наилучшее вращение можно найти, минимизируя стандартное отклонение, после того, как список был забит голубем:

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]

Хотя это можно было бы оптимизировать в дальнейшем, он довольно быстро принимает 0,0013s для 20 номеров. Выполнение быстрого сравнения с ответом @Mo Tao, используя 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 to [145, 145, 145] in 0.002s

# Mo Tao 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 to [145, 145, 145] in 1.095s

Этот метод также, как представляется, находит оптимальное решение во многих случаях, хотя это, вероятно, не будет выполняться для всех случаев. Проверяя эту реализацию 500 раз, используя список из 30 чисел против ответа Мо Тао и сравнивая, суммируются ли субки с тем же количеством:

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)

Я думал, что предоставил обновление с более оптимизированной версией моей функции здесь:

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

Основное изменение заключается в том, что поиск хорошего порядка останавливается, как только подходящее вращение найдено. Также выполняется поиск только отсортированного списка в обратном порядке, который, как представляется, не изменяет результат. Сроки этого с

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

приводит к большой скорости. На моем текущем компьютере rotate занимает около 1,84 мс, а rotate2 занимает около 0,13 мс, что примерно равно 14 раз. Для сравнения реализация גלעד ברקן заняла около 0,99 мс на моей машине.

Ответ 2

Как я упоминал в комментарии к вопросу, это прямолинейный метод динамического программирования. Это занимает менее 1 секунды для s = range(1, 30) и дает оптимизированное решение.

Я думаю, что код сам объясняется, если вы знаете Memoization.

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)

Ответ 3

Я бы сказал, что ваша жадная функция действительно дает хорошие результаты, но имеет тенденцию становиться очень медленной, если размер ввода больше, чем 100.

Но вы сказали, что размер вашего ввода фиксирован в диапазоне - 10,30. Следовательно, жадное решение на самом деле неплохое. Вместо того, чтобы стать слишком жадным в самом начале. Я предлагаю сначала стать ленивым и стать жадным в конце.

Вот измененная функция 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

Что он делает, так это сначала сортирует вход в порядке убывания и заполняет элементы в трех подписях один за другим, пока осталось около 6 элементов. (Вы можете изменить это ограничение и проверить, но для размера 10-30 Я думаю, что это самое лучшее)

Когда это делается, просто продолжайте с жадным подходом. Этот метод занимает очень мало времени и точнее, чем жадное решение в среднем.

Вот график зависимости размера от времени -

и размер по сравнению с точностью -

Точность - это стандартное отклонение от среднего значения окончательных подписок и исходного списка. Поскольку вы хотите, чтобы столбцы располагались на почти одинаковой высоте, а не на высоте (в среднем исходного списка).

Кроме того, диапазон значений элемента находится между 3-15, так что сумма вокруг 100-150, как вы упомянули.

Это тестовые функции -

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

Вот полный файл.

Изменить -

Я тестировал kezzos ответ для точности, и он выполнял действительно хорошо. Отклонение оставалось меньше .8 все время.

Среднее стандартное отклонение в 100 прогонов.

  Lazy Pigeon     Pigeon         Rotation
  1.10668795      1.1573573      0.54776425

В случае скорости, порядок довольно высок для сравнения функции вращения. Но 10 ^ -3 отлично, если вы не хотите повторно запускать эту функцию.

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

Вот гистограмма, сравнивающая точность всех трех функций. -

В целом, решение kezzos лучше всего, если вы в порядке со скоростью.

Html файлы plotly - против времени, в сравнении с точностью и гистограмма.

Ответ 4

Мы можем исследовать устойчивость найденного решения в отношении замены элементов между найденными списками. Ниже я разместил свой код. Если мы сделаем целевую функцию лучше с помощью замены, мы продолжим поиск списков и продолжаем надеяться, что мы снова сделаем функцию лучше с другой заменой. В качестве отправной точки мы можем принять ваше решение. Конечный результат будет чем-то вроде локального минимума.

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

Интересно, что этот подход хорошо работает, даже если мы начнем с произвольного 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

Он предоставляет другой результат, но то же значение функции.

Ответ 5

Здесь моя ореховая реализация Korf 1 Секвенциальное числовое разбиение (SNP), но оно использует только Кармаркар-Карп, а не полный Кармаркар-Карп для двухстороннего раздела (я включил неиспользуемую, несколько неудовлетворительную версию CKK - возможно, у кого-то есть предложение сделать ее более эффективной?). На первом подмножестве он устанавливает нижнюю и верхнюю границы. См. Статью, на которую ссылается. Я уверен, что более эффективные реализации могут быть сделаны. Изменить MAX_ITERATIONS для улучшения результатов по сравнению с более длинным ожиданием:)

Кстати, функция KK3 (расширение Кармаркар-Карпа на трехстороннее разбиение, используемое для вычисления первой нижней границы), кажется довольно хорошим сама по себе.

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 Ричард Э. Корф, многоканальное разделение номеров, отдел компьютерных наук Калифорнийского университета, Лос-Анджелес; aaai.org/ocs/index.php/IJCAI/IJCAI-09/paper/viewFile/625/705