最大化最小平均组值的算法组/排序列表

Question

我正在寻找一些帮助来用Python编写一个实现以下功能的算法：

Given a list of real numbers, sort/group the list into n smaller lists such that the average minimum group value is maximized.

例如，考虑将下面的列表分成两个列表—A和B，每个列表都有两个元素。在

lis = [1,1,2,2]

在下面的第一个场景中，每个列表的最小值为1，因此平均最小值为1。在

^{pr2}$

在第二个场景中，A的最小值为1，B的最小值为2，因此平均最小值为1.5。这种安排是最好的。在

很明显，最好将“相似”的价值观分组。我可以用Jenks natural breaks optimization（或一维k-均值聚类）来实现这一点。但是，我不确定我的目标和Jenks优化的目标是否（数学上）相等。在

任何帮助或意见将不胜感激。在

编辑：较小的列表必须具有相同的大小（假设给定的列表总是分成没有剩余的较小的组）。在

Answer 1

解决这个问题的最好方法是将数字从最小到最大排序，然后将排序后的列表拆分为n组，而无需进一步重新排列。对这个分组的任何改进尝试都会降低其中一个组的最小值，从而降低最小值的平均值。在

一个例子可能有助于解释原因。

给出一个有12个数字的列表：

[94, 82, 61, 2, 96, 34, 87, 13, 82, 91, 61, 39]

排序后的列表是：

^{pr2}$

如果我们想要n=3组，那么这些组是：

[[2, 13, 34, 39], [61, 61, 82, 82], [87, 91, 94, 96]]

所以最小值的平均值是avg(2,61,87)=50。在

你能做得更好吗？答案是否定的。

从一组A移动到另一组B将减小A的最小值，而不相应地增加B的最小值

例如，你可能会认为把61岁调到另一个小组会有帮助。在

一种可能的重新安排是：

[[2, 13, 34, 61], [39, 61, 82, 82], [87, 91, 94, 96]]

这个重排的值是avg(2,39,87)=42。在

另一种可能的重新安排是：

[[2, 13, 34, 39], [87, 61, 82, 82], [61, 91, 94, 96]]

此重新排列的值为avg(2,61,61)=41。在

所以你看，我们不可能通过移动61来做得更好。同样，我们不能通过移动任何数字来做得更好。在

Answer 2

似乎最简单的方法是对列表进行初始排序，以便始终将最低值分组在一起，例如：

# Define the list of values to group
values = [1, 2, 3, 10, 11, 12]

# Sort the values
values.sort()

# Split the values down into an even number of `n` groups
no_groups = 3
group_size = len(values) / no_groups
groups = []

for i in range(0, no_groups):
    groups.append(values[0:(group_size)])
    values = values[group_size:]

# Calculate the average minimum value of the groups
average_min = float(sum([g[0] for g in groups])) / no_groups

print(average_min)

但是考虑到你提到的Jenks和K-means集群，我担心这太简单了，我遗漏了什么？在