Picking out exacly one value from each row and column of a matrix

2
votes

This is not exactly a question about code, but I need some help with the logic of the algorithm.

Given an NxN matrix which has at least one zero value on each row and column, how would you chose N zeros so that there is exactly one value on each row and each column? For example:

0 4 6 0 2
0 8 9 5 0
4 0 9 8 5
0 8 0 1 3
8 6 0 1 3

Clearly, you first have to choose the zeros that are singular on each row or column. I am not sure about the case when there is an equal number of zeros on several rows and columns. How would I pick the optimal values so that no line or column is left out?

2
algorithmmatrix
use recursion with backtracking. Any solution will do. Iff it is not fast enough will you need a faster algorithm. For example it makes sense to choose the rows in order of least possible zeroes so that you start from the 3rd row, then 5th. – Antti Haapala

2 Answers

2
votes

This is the problem of finding a maximum cardinality matching in a bipartite graph: the rows represent one set of vertices u_1, u_2, ..., u_N, the columns the other set v_1, v_2, ..., v_N, and there is an edge u_i -- v_j whenever there is a 0 at matrix position (i, j).

It can be solved using maximum flow algorithms such as Ford-Fulkerson in O(N^3) time, or with the more specialised Hopcroft-Karp algorithm in O(N^2.5) time. In fact these algorithms solve a slightly more general problem: It will find a largest-possible set of unique (row, column) pairs such that each pair has a 0 in the matrix. (In your case, you happen to know that there is a solution with N such pairs: this is obviously best-possible.)

0
votes

  1. Select the row with least number of zeros.

  2. For every zero in that row, pick the one whose column has the least number of zeros.

  3. Mark that row and column in some way (maybe remove all zeors from them after storing the index of the selected zero? This one is up to you).

    The marked rows and columns are skipped in the next iteration.

  4. Repeat until all unmarked rows and columns are traversed, or until a further solution can't be built.

So for the sample problem, this is how the solution can be visualized ( < and ^ represent marked rows and columns ):

0 4 6 0 2

0 8 9 5 0

4 0 9 8 5

0 8 0 1 3

8 6 0 1 3 // Row with least zeros, and last one to be accessed

Iteration 1:

0 4 6 0 2

0 8 9 5 0

4 0 9 8 5

0 8 0 1 3

8 6 0 1 3 <

_ _ ^ _ _

Iteration 2:

0 4 6 0 2

0 8 9 5 0

4 0 9 8 5 <

0 8 0 1 3

8 6 0 1 3 <

_ ^ ^ _ _

Iteration 3:

0 4 6 0 2

0 8 9 5 0 <

4 0 9 8 5 <

0 8 0 1 3

8 6 0 1 3 <

_ ^ ^ _ ^

Iteration 4:

0 4 6 0 2 <

0 8 9 5 0 <

4 0 9 8 5 <

0 8 0 1 3

8 6 0 1 3 <

_ ^ ^ ^ ^

Iteration 5:

0 4 6 0 2 <

0 8 9 5 0 <

4 0 9 8 5 <

0 8 0 1 3 <

8 6 0 1 3 <

^ ^ ^ ^ ^