排列矩阵

Question

能否将一个有n行n列的矩阵A分解成n x n个置换矩阵之和，其中每行和每列中1的数量为m？

更新： 是可以的。下面展示了这样一个例子 - 但我们如何推广这个答案？

- user1031010

---

假设您分解矩阵的第一行，它们的总和不等于A的第一行，这是什么意思？那么m是什么呢？所有行和列中1的数量相同吗？ - Saeed Amiri

你的样本分解包含一些错误：第一个排列矩阵中的(1,4)元素和第二个排列矩阵中的(2,4)元素应该为零。 - Jeffrey Sax

抱歉，我已经相应地更新了。 - user1031010

Answer 1

这可以很容易地使用递归（回溯或深度优先遍历）算法完成。以下是其解决方案的伪代码：

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);

- monish001

Answer 2

对于第一个排列矩阵，取第一行中的第一个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,1)作为第一行，选择(2,2)作为第二行，选择(3,3)作为第三行，选择(4,4)作为第四行。然后我们有：

    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行中被取走了。如果你有两列这样的情况，其中一列必须在之前被选为最小列。

- Jeffrey Sax

---

如果我理解你的算法正确的话，这个方法对于所有的矩阵都不适用。考虑一下问题中的矩阵A。尝试在该矩阵上运行第二次迭代。 - user1031010

Answer 3

你想要的是一个叫做1-factorization的东西。有一种算法是重复地寻找完美匹配并将其移除；可能还有其他算法。

- basename