Разделите список на три списка, чтобы их сумма была близка друг к другу
Скажем, что у меня есть массив чисел S = [6, 2, 1, 7, 4, 3, 9, 5, 3, 1]. Я хочу разделить на три массива. Порядок количества и количества элементов в этом массиве не имеет значения.
Пусть говорят, что A1, A2 и A3 являются вспомогательными массивами. Я хочу свести к минимуму функцию
f(x) = ( SUM(A1) - SUM(S) / 3 )^2 / 3 +
( SUM(A2) - SUM(S) / 3 )^2 / 3 +
( SUM(A3) - SUM(S) / 3 )^2 / 3
- Мне не нужно оптимальное решение; Мне просто нужно хорошее решение.
- Я не хочу, чтобы алгоритм был слишком медленным. Я могу обменять некоторую скорость для лучшего результата, но я не могу торговать слишком много.
- Длина S составляет от 10 до 30.
Почему
Почему мне нужно решить эту проблему? Я хочу красиво расположить ящик на три столбца, так что общая высота каждой колонки не слишком отличается друг от друга.
![Введите описание изображения здесь]()
Что я пробовал
Мой первый инстинкт - использовать жадные. Результат не так уж плох, но он не обеспечивает оптимальное решение. Есть ли лучший способ?
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)
Ответы
Ответ 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
Вот гистограмма, сравнивающая точность всех трех функций. -
![Базовая диаграмма sd]()
В целом, решение 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
