Minimize the sum of columns in a matrix by permuting elements in python
I have the following matrix:
([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 goal is to determine the optimal way to sort the items in different rows to minimize the maximum item in the sum of the columns.
For example, one of the possibilities:
([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.
The easiest way to do this is to check all possible permutations, but this method gets incredibly slow in python as the matrix grows.
Any idea to make it faster?
source to share
First reinforce your claim you might be asking
"Can I produce a matrix that minimizes the difference between the max sum and the min sum of each column in my matrix"
This is good because:
- This will satisfy your original requirement, so resolving that question solves your question.
- With this requirement, it's easy to show suboptimality at every iteration so that we can convince ourselves that the greedy approach will work.
To implement a greedy solution, just hold the current amount of your checkmate, and for each row, insert the lowest value in the current row into the column with the highest amount. This will ensure that the column is as complex as possible.
It will take m
inserts for each row n
and 2mlogm
sorting of each row, so it should work for O(n*m + n*2*mlogm)
, therefore 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)
Output:
>> [2, 5, 5, 10]
>> [7, 1, 4, 1]
>> [3, 9, 3, 1]
[12, 15, 12, 12]
source to share
Here's the idea:
- Select the 2 columns with the lowest and highest amount. Pay attention to their difference, d.
- Examine the items in both columns. Find the row with the largest absolute value of the difference d 'so that d' <d and d '> 0.
- Swap this line.
- Repeat steps 1-3 until step 2 is no longer possible.
Example: Given,
([2, 5, 5, 10]
[7, 1, 4, 1]
[1, 3, 3, 9])
We select the 2 columns with the smallest and largest sum. Here you have Column 1 with the lowest amount and Column 3 with the largest amount. For these two columns, the difference between their sums d is 11.
([5, 10]
[1, 1]
[3, 9])
Now we will find the greatest difference d 'such that d' d and d '> 0 such that 9 - 3 = 6
. We are now replacing the elements on this line. So we have
([2, 5, 5, 10]
[7, 1, 4, 1]
[1, 9, 3, 3])
This matrix has a column sum [10, 15, 12, 14]
Repeat the above process one more time, then you get this:
([5, 2, 5, 10]
[7, 1, 4, 1]
[1, 9, 3, 3])
This resulting matrix has a sum [13, 12, 12, 14]
. At this point, step 2 is no longer possible. So we are done.
source to share