通過在python重排列的元件最小化在矩陣列的總和

Question

我有以下矩陣：

([2, 5, 5, 10] 
[7, 1, 4, 1] 
[1, 3, 3, 9]) 

如果列相加的結果爲：

[10, 9, 12, 20] 

我的目標是確定最佳可以對不同行中的元素進行排序，以便將列總和中的最大元素最小化。

例如，一種可能性是：

([2, 5, 5, 10] 
[7, 1, 4, 1] 
[1, 9, 3, 3]) 

如果列相加的結果爲：

[10, 15, 12, 14] 

這是比第一個較好的解決。

最簡單的方法是檢查所有可能的排列，但是隨着矩陣的增長，這種方法在Python中變得非常慢。

任何想法以更快的方式做到這一點？

Answer 1

首先讓加強你的要求，你可以問

"Can I produce a matrix that minimizes the difference between the max sum and the min sum of each column in my matrix" 

這是一件好事，因爲：

1. 它會滿足你的原始需求，從而解決這一解決你的問題
2. 關於該要求是容易在每次迭代中顯示次優性，因此我們可以說服自己，貪婪的方法正在發揮作用。

要實現一個貪婪的解決方案，只需保持您的墊的運行總和，併爲每一行插入當前行中的最低值到最高總和列。這確保了色譜柱儘可能均勻堆積。

這將需要m插入爲每個n行和2mlogm各種每一行的所以應該在O(n*m + n*2*mlogm)所以O(nmlogm)運行。

output_mat = [] 

input_mat = [ 
    [2, 5, 5, 10], 
    [7, 1, 4, 1], 
    [1, 3, 3, 9], 
] 

row_size = len(input_mat[0]) 
running_sum = [0] * row_size 

for row in input_mat: 
    sorted_idx = [ 
     x[0] for x in 
     sorted(enumerate(row), key=lambda x: x[1]) 
    ] 

    sum_sorted_idx = [ 
     x[0] for x in 
     sorted(enumerate(running_sum), key=lambda x: x[1], reverse=True) 
    ] 

    new_val_row = [None] * row_size 
    for col_idx,val_idx in zip(sum_sorted_idx, sorted_idx): 
     new_val_row[col_idx] = row[val_idx] 
     running_sum[col_idx] += row[val_idx] 

    output_mat.append(new_val_row) 

for x in output_mat: 
    print ">> %s" % x 
print(running_sum) 

輸出：

>> [2, 5, 5, 10] 
>> [7, 1, 4, 1] 
>> [3, 9, 3, 1] 
[12, 15, 12, 12] 

Answer 2

這裏有一個想法：

1. 選擇2列與最小和最大總和。注意它們的區別，d。
2. 檢查兩欄中的元素。找到與差d的最大絕對值的行「使得d」 < d和d」> 0
3. 交換該行中的元素。
4. 重複步驟1-3，直到步驟2不再可能。

例子： 鑑於

([2, 5, 5, 10] 
[7, 1, 4, 1] 
[1, 3, 3, 9]) 

我們挑兩列用最小和最大總和。這裏我們有最小和的第1列和最大和的第3列。 對於這些2列，它們的和的差，d，是11

([5, 10] 
[1, 1] 
[3, 9]) 

現在，我們發現最大的區別d '這樣d' < d和d」 > 0，即9 - 3 = 6。 我們現在交換該行中的元素。因此，我們有

([2, 5, 5, 10] 
[7, 1, 4, 1] 
[1, 9, 3, 3]) 

這個矩陣已經[10, 15, 12, 14]

重複以上過程一次的列 - 和，那麼你將結束與以下：

([5, 2, 5, 10] 
[7, 1, 4, 1] 
[1, 9, 3, 3]) 

這導致基體具有總和爲[13, 12, 12, 14]。此時，步驟2不再可能。所以我們完成了。