通过在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不再可能。所以我们完成了。