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

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來做得更好。同樣，我們也無法通過移動任何數字來做得更好。