Reputation: 63

Iterative Reduction to Null Matrix

Here's the problem: I'm given a matrix like

Input:

1 1 1
1 1 1
1 1 1

At each step, I need to find a "second" matrix of 1's and 0's with no two 1's on the same row or column. Then, I'll subtract the second matrix from the original matrix. I will repeat the process until I get a matrix with all 0's. Furthermore, I need to take the least possible number of steps.

I need to print all the "second" matrices in O(n) time. In the above example I can get to the null matrix in 3 steps by subtracting these three matrices in order:

Expected output:

I have coded an attempt, in which I am finding the first maximum value and creating the second matrices based on the index of that value. But for the above input I am getting 4 output matrices, which is wrong:

My output:

My solution works for most of the test cases but fails for the one given above. Can someone give me some pointers on how to proceed, or find an algorithm that guarantees optimality?

Test case that works:

Input:

0 2 1
0 0 0
3 0 0

Output

Upvotes: 3

Answers (5)

rici

Reputation: 241901

I'm pretty sure that this is some kind of variant of the exact cover problem, which is known to be NP-complete. Your proposed algorithm is a simple greedy solution. The problem with greedy solutions is that they often work well enough to convince you that greed is good and then suddenly leave you high and dry looking for a better solution. (Consider the global economy, for example.) Anyway, Knuth's Dancing Links technique is a standard way of solving the problem (exact set cover, not global economy).

Upvotes: 0

threenplusone

Reputation: 2122

Summing of each row / column and taking the largest of those sums gives you the optimal number of matrix subtractions required to reduce to a null matrix.

For example:

1 2 4 0 = 7
2 2 0 1 = 5
0 0 1 0 = 1
3 0 2 1 = 6
= = = =
6 4 7 2

Which means that this matrix will take 7 optimal subtractions to empty.

I believe that counting backwards from this and removing from columns / row with that value will solve your problem (I am not sure of an efficient way of selecting these - brute force?).
You can also use your previous method to remove extra elements.

For example (using the above matrix).

Step 7:
We must subtract from row 1 & column 3.

Solves this, so now we can use your previous method to remove "bonus" elements.

Now apply the sum of each row / column again and continue for the next step.

Step 6:

1 2 3 0 = 6
1 2 0 1 = 4
0 0 1 0 = 1
3 0 2 0 = 5
= = = =
5 4 6 1

Next subtraction:

And so on.

Note: This still does not work very well with "all 1" matrices, as you get stuck on the problem of selecting 1 from every row and column (same as you did in your example).

But someone may be able to extend my solution.

Upvotes: 1

paulsm4

Reputation: 121809

1) If all you want to do is iterate through all the elements in your matrix...

2) then all you have to do is loop for (int i=0; i < rows*cols; i++) {} ...

3) And such a loop is ALREADY O(n) (i.e. it increases LINEARLY with the #/elements in your matrix)

Upvotes: 0

threenplusone

Reputation: 2122

I'm not entirely sure if this is what you are after, but could you create a list of available columns and mark them as used for each iteration.

For Example:

repeat until an empty matrix
  mark all columns as available
  for each row
    find the maximum value in all available columns and store it's coordinates
    mark that column as unavailable
  print, decrement and clear the list of stored coordinates

This doesn't work, but it does show the algorithm that user1459032 is using.

Upvotes: 0

Sajal Jain

Reputation: 708

Let Number of rows = Number of columns = N

for iteration=1:N
  for row=1:N
      cell(row,(row+iteration)%N) := 0

Number of iterations is N. In every iteration N one's will be changed to 0

Upvotes: 0

Iterative Reduction to Null Matrix

Answers (5)

Related Questions