将列表分成三个列表,使它们的总和彼此接近
假设我有一个数字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)
正如你所说,你不介意非最佳解决方案,我虽然会重新使用你的初始函数,并添加一种方法来为你的初始列表找到一个好的起始安排 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]
虽然这可以进一步优化,但是对于20个数字,它可以很快地获得0.0013秒.使用@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'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
在许多情况下,这种方法似乎也找到了最佳解决方案,尽管这可能不适用于所有情况.使用30个数字列表对Mo Tao的答案进行500次测试,并比较子列表总和是否相同:
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大约rotate2需要1.84毫秒,大约需要0.13毫秒,所以大约需要14倍的加速.为了比较,我的机器上的实现大约需要0.99ms.
我们可以研究您找到的解决方案在替换找到的列表之间的元素方面的稳定性。下面我放置了我的代码。如果我们通过替换使目标函数变得更好，我们会保留找到的列表，并进一步希望通过另一个替换使该函数再次变得更好。作为起点，我们可以采用您的解决方案。最终结果将类似于局部最小值。
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
它提供了不同的结果但函数的值相同。