I'm trying to find out which is the best approach for this problem: There is a matrix like this: 1 0 0 1 0 1 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 0 1 0 0 We want to find out every possible matrix where only one 1 is in each row and column, for example this matrix is a possible solution: 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 I think you can find a solution with looping throug each possible combination and check if there is exactly one 1 in each row and column? Is there any known algorithm for this? Is is possible to actually calculate the solution and not trying out every possibility? Thank you very much! Edit: One possible solution (but expensive) could be to generate every theoretically possible matrix, for example (using 3x3 matrix because it's shorter): 1. 1 0 0 0 1 0 0 0 1 2. 1 0 0 0 0 1 0 1 0 3. 1 0 0 0 0 1 0 1 0 4. 0 1 0 1 0 0 0 0 1 5. 0 1 0 0 0 1 1 0 0 etc. Then we could check for every generated matrix if the original matrix has the 1s at the given positions. If yes, it's a solution. Which loops would you need to generate all these matrices?

exactly one value in each row and column of a matrix

Reputation: 11

It's a bipartite matching problem.

Consider a bipartite graph with r vertices in one set (R) and c vertices in the other set (C) where r and c are number of rows and columns, respectively. The edge between vertex i (in set R) and vertex j (in set C) exist iff element [i,j] is 1 in given matrix.

If you want to find matrices with maximum number of 1's (Maximum Bipartite Matching) you can use

Maximum Bipartite Matching using Ford-Fulkerson algorithm running in O(V.E)

or

Hopcroft–Karp Algorithm for Maximum Matching running in O(sqrt(V).E)

Upvotes: 1

beaker

Reputation: 16801

Edit:

Based on your comment, I re-read the original question and realized that I had totally missed the point of the problem. I'll post a (hopefully) more relevant answer here, but folks should feel free to revoke any upvotes. I debated posting a new answer and deleting this one and can still do that if folks think that's the way to go.

New Answer:

Here's how I understand your problem now. Given a square binary matrix A, find all matrices B such that the sum of the elements in each row of B is 1 and the sum of the elements in each column is 1 and for all elements B(r,c) == 1, the corresponding element from the original matrix A(r,c) == 1.

Edit 2:

The problem here is that you want to find all of the solutions. And there are a lot of them. For an nxn matrix of all 1's you're going to have n! solutions. For a matrix where each row has m 1's, you'll potentially have something like

m^n-m * m!

solutions. So even if you had a non-deterministic algorithm to generate all of your solutions in O(1) time, the time complexity of simply printing them out would still be exponential.

As mentioned by MrSmith42 in the comments, you're probably going to need to do a backtracking search, but there are a couple of things you can do to reduce the search space:

The simplest check you can make is to look for rows/columns in A that have only one 1 in them already. (Obviously, if there are any rows/columns with no 1's in them, there are no valid solutions.) If row r has only one 1 in column c, set all other elements in column c to 0. Likewise, if column c has only one 1 in row r, set all other elements in row r to 0. In your example:

1 0 0 1 0     1 0 0 1 0     1 0 0 1 0
1 1 0 1 0     1 1 0 1 0 ==> 0 1 0 0 0
1 1 0 0 1 ==> 0 0 0 0 1     0 0 0 0 1
0 0 1 1 0     0 0 1 1 0     0 0 1 1 0
1 0 1 0 0     1 0 1 0 0     1 0 1 0 0

There is only one 1 in column 5, so row 3 in B must have a 1 at B(3,5) in order to be valid. This means that we can modify our input matrix A and reduce the search space (slightly) without losing any valid solutions. From here you now have only one 1 in column 2 and can set the other values in row 2 to 0.

Next you can use forward-checking during the search to prevent searching submatrices where it is impossible that a valid solution can be found. Say you're given the following matrix:

There are no rows or columns with only one 1, so we start assigning values. Assume we've following our backtracking algorithm to the point where (in Step 1) we've assigned column 4 to row 1. We'll set the other entries in row 1 and column 4 to x to indicate that they've already been assigned:

               Step 1        Step 2
1 0 0 1 0 ==> x x x 1 x     x x x 1 x
0 1 1 0 1     0 1 1 x 1 ==> x x 1 x 1
1 1 0 0 1     1 1 0 x 1     1 1 x x 1
0 0 1 1 0     0 0 1 x 0     0 0 x x 0
1 0 1 0 0     1 0 1 x 0     1 0 x x 0

In Step 2 we assign column 3 to row 2 and set the row and column to assigned.

Notice that in row 4 we don't have any 1's left so it is impossible to get a valid solution with this assignment. We can immediately backtrack to try different assignments for rows 2 and 1.

Original (Wrong) Answer

Every possible nxn matrix with exactly one 1 in each row and column and the rest 0's is a permutation of the identity matrix. That is, for n=5, you can get every valid matrix of this type by swapping rows (or, equivalently, columns) of the matrix:

If you swap the last to rows, for example, you get:

To automatically generate all of the possible valid matrices, you first give each row of the identity matrix an index, say 1-5 from top to bottom:

1- 1 0 0 0 0
2- 0 1 0 0 0
3- 0 0 1 0 0
4- 0 0 0 1 0
5- 0 0 0 0 1

You then simply generate all of the n! possible permutations of {1, 2, 3, 4, 5}. An ordering of {1, 2, 3, 5, 4} would give you the second matrix above.

Upvotes: 3

karl71

Reputation: 1092

I've written this simple code (using your matrix):

A=[1 0 0 1 0;
1 1 0 1 0;
1 1 0 0 1;
0 0 1 1 0;
1 0 1 0 0]

[row,col]=size(A);
B=zeros(row,col);

for i=1:col

    [one_row,~]=find(A(:,i)==1); %one_row says in wich row of the "i" column there are ones
    where_row=min(one_row); %we're interested only in one of those "ones".I'm taking the first found
    B(where_row,i)=1; %inserting in the output matrix
end

B %for visualization purposes

I hope it works for you.