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

Question

我在寻找一些帮助用Python写一个算法，完成以下操作：

鉴于实数列表，排序/组列入n个较小的列表，以使平均最小组值最大化。

例如，考虑将以下列表分为两个列表 - A和B，每个列表包含两个元素。

lis = [1,1,2,2] 

在下面的第一个方案中，每个列表的最小值是1，并且这样的平均最小值为1。

# Scenario 1 
A = [1,2] 
B = [1,2] 

# Scenario 2 
A = [1,1] 
B = [2,2] 

在第二场景中，A的最小值是1，B的最小值为2，所以平均最小值为1.5。这种安排是最佳的。

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

任何帮助或输入，将不胜感激。

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

Answer 1

看起来好像最简单的方法是先对列表进行排序，这样的最低值总是组合在一起，例如：

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

但考虑到你的詹克斯的提及和K-均值聚类I”我担心这太简单了，我错过了什么？

Answer 2

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

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

鉴于有12个号码的清单：

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

排序列表是：

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

如果我们想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来做得更好。同样，我们也无法通过移动任何数字来做得更好。