通过置换python中的元素来最小化矩阵中的列总和 [英] Minimize sum of columns in matrix by permutating elements in python

问题描述

我有以下矩阵:

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

如果对列进行求和，则结果为:

If the columns are summed the result is:

[10, 9, 12, 20]

我的目标是确定对不同行中的元素进行排序的最佳方法，以最大程度地减少列总和中的最大元素.

My objective is to determine the optimum way to sort the elements in the diferent rows in order to minimize the maximum element in the sum of columns.

例如，一种可能性是:

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

如果对列进行求和，则结果为:

If the columns are summed the result is:

[10, 15, 12, 14]

这是比第一个更好的解决方案.

This is a better solution than the first one.

最简单的方法是检查所有可能的排列，但是随着矩阵的增长，这种方法在python中变得非常慢.

The easiest way to do this is checking all the possible permutations, but this method gets incredible slow in python as the matrix grows.

有什么想法可以更快地做到这一点吗?

Any idea to do this in a faster way?

推荐答案

首先让我们加强您可能会问的要求

First lets strengthen your requirement you could ask

"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. 有了此要求，很容易在每次迭代中显示次优状态，因此我们可以说服自己贪婪的方法行之有效.

要实施贪婪的解决方案，只需保持席子的运行总和，然后为每行将当前行中的最小值插入最高和列中.这样可确保色谱柱尽可能均匀地堆放.

To implement a greedy solution just hold a running sum of your mat and for each row insert the lowest value in the current row into the highest sum column. This ensure that the column are as evenly stacked as possible.

这将对n行的每一行进行m插入，并对每一行进行2mlogm排序，因此应在O(n*m + n*2*mlogm)处运行，因此O(nmlogm).

This will take m inserts for each of n rows and 2mlogm sorts of each row so should run at O(n*m + n*2*mlogm) so 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]

这篇关于通过置换python中的元素来最小化矩阵中的列总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！