能否将一个有n行n列的矩阵A分解成n x n个置换矩阵之和,其中每行和每列中1的数量为m?
更新: 是可以的。下面展示了这样一个例子 - 但我们如何推广这个答案?
更新: 是可以的。下面展示了这样一个例子 - 但我们如何推广这个答案?
这可以很容易地使用递归(回溯或深度优先遍历)算法完成。以下是其解决方案的伪代码:
void printPermutationMatrices(const int OrigMat[][], int permutMat[], int curRow, const int n){
//curPermutMatrix is 1-D array where value of ith element contains the value of column where 1 is placed in ith row
if(curRow == n){//Base case
//do stuff with permutMat[]
printPermutMat(permutMat);
return;
}
for(int col=0; col<n; col++){//try to place 1 in cur_row in each col if possible and go further to next row in recursion
if(origM[cur_row][col] == 1){
permutMat[cur_row] = col;//choose this col for cur_row
if there is no conflict to place a 1 in [cur_row, col] in permutMat[]
perform(origM, curPermutMat, curRow+1, n);
}
}
}
以下是如何从您的主函数中调用:
int[] permutMat = new int[n];
printPermutationMatrices(originalMatrix, permutMat, 0, n);
对于第一个排列矩阵,取第一行中的第一个1。对于第二行,取第一个在你还没有的列中的1。对于第三行,取第一个在你还没有的列中的1。以此类推,对所有行进行操作。
现在你有了一个排列矩阵。
接下来从原始矩阵中减去第一个排列矩阵。这个新矩阵每行和每列都有m-1
个1。所以重复这个过程m-1
次,你就会得到m
个排列矩阵。
你可以跳过最后一步,因为每行和每列只有一个1的矩阵已经是一个排列矩阵了。不需要进行任何计算。
这是一种贪心算法,不总是有效。我们可以通过稍微改变选择规则来使其有效。见下文:
以你的例子为例:
1 0 1 1
A = 1 1 0 1
1 1 1 0
0 1 1 1
1 0 0 0 0 0 1 1
A = 0 1 0 0 + 1 0 0 1
0 0 1 0 1 1 0 0
0 0 0 1 0 1 1 0
第一个矩阵是置换矩阵。第二个矩阵每行和每列恰好有两个1。所以我们按顺序选择:(1,3),(2,1),(3,2) 然后...出现问题了:包含第4列1的行已经被使用过了。
那么我们该如何解决呢?我们可以跟踪每列剩余的1的数量。我们不再选择未使用的第一列,而是选择剩余1最少的列。对于上述第二个矩阵:
0 0 1 1 0 0 X 0 0 0 X 0 0 0 X 0
B = 1 0 0 1 --> 1 0 0 1 --> 0 0 0 X --> 0 0 0 X
1 1 0 0 1 1 0 0 1 1 0 0 X 0 0 0
0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
------- ------- ------- -------
2 2 2 2 2 2 X 1 1 2 X X X 1 X X
因此,在第二步中我们会选择第4列,在第三步中选择第1列,在第四步中选择第2列。
总是只能有一列剩下一个1。其他的1必须在前面的m-1
行中被取走了。如果你有两列这样的情况,其中一列必须在之前被选为最小列。