python - 将列表拆分为 N 个子列表，总和大致相等

Question

我有一个整数列表，我需要将其拆分为给定数量的子列表（对每个子列表的顺序或元素数量没有限制），以最小化每个子列表总和的平均差异。

例如：

>>> x = [4, 9, 1, 5]
>>> sublist_creator(x, 2)
[[9], [4, 1, 5]]

因为list(map(sum, sublist_creator(x, 2)))产量[9, 10]，最小化平均距离。或者，[[9, 1], [4, 5]]同样正确，我的用例在两种可能性之间没有偏好。

我能想到的唯一方法是通过迭代检查所有可能的组合，但我正在处理一个约 5000 个元素的列表，并且需要将其拆分为约 30 个子列表，因此这种方法非常昂贵。

标签： pythonpython-3.x

Answer 1

这是大纲：

1. 创建N空列表
2. sort()您的输入数组按升序排列
3. pop()排序数组中的最后一个元素
4. append()弹出的元素到具有最低元素的列表sum()中
5. 重复 3 和 4 直到输入数组为空
6. 利润！！！

对于 M=5000 个元素和 N=30 个列表，如果您仔细存储子列表的中间和而不是每次都从头开始计算它们，这种方法可能需要大约 O(N*M)。