矩阵的每一行和每列中只有一个值

Question

我试图找出解决这个问题的最佳方法:有一个像这样的矩阵:

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

我们想要找出每个可能的矩阵,其中每行和每列只有一个1,例如这个矩阵是一个可能的解决方案:

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

我想你可以找到一个解决方案,通过每个可能的组合循环,并检查每行和每列中是否只有一个1？有没有任何已知的算法？有可能实际计算解决方案而不是尝试所有可能性吗？

非常感谢你!

编辑:一种可能的解决方案(但价格昂贵)可能是生成每个理论上可能的矩阵,例如(使用3x3矩阵,因为它更短):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

等等

然后,如果原始矩阵在给定位置具有1,则我们可以检查每个生成的矩阵.如果是的话,这是一个解决方案.

您需要哪些循环来生成所有这些矩阵？

Answer 1

我写了这个简单的代码（使用你的矩阵）：

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

我希望这个对你有用。