生成所有可能的二进制矩阵，使得每一行和每一列的总和为每个矩阵的AT MOST 1

Question

我正在尝试为给定的n生成所有可能的平方二进制矩阵，使得：对于每个二进制矩阵：

1) the rows sum up to at most 1
2) the columns sum up to at most 1

示例：对于n = 2，有效矩阵为：

[0 0]
[0 0]

[0 0]
[0 1]

[0 0]
[1 0]

[0 1]
[0 0]

[0 1]
[1 0]

[1 0]
[0 0]

[1 0]
[0 1]

我需要生成所有这些矩阵

在python中，对于n = k，我现在有以下蛮力方式可以做到这一点>

    allwords = list(it.product(*([(0, 1)] * (n**2)))) # Generate all possible binary matrices
    allarrays = map(np.asarray, allwords)  # Convert to array # Convert them toarray
    allmatrices = [a.reshape(n, self.n) for a in allarrays]  # Matrixify # Make a matrix
# The following checks if the matrix has row sum at most 1 and column sum at most 1
    validActions = [x for x in allmatrices if contains(x)]  # Final list has only vlaid matrices
包含定义为

def contains(x): # Checks if row and column sums are at most 1 for each entry
        colSums = np.sum(x, axis=0)
        rowSums = np.sum(x, axis=1)
        return (np.all(colSums <= 1) and np.all(rowSums <= 1)) and np.all(x >= 0)
n = 5或更高时，这几乎中断了，所以我需要一种更聪明的方法来做到这一点。

目标是最终创建用于增强学习的离散状态空间，并将该离散状态空间中的每个条目映射到有效的二进制矩阵。有效的二进制矩阵是行和列的总和不超过1的矩阵。

我正在尝试为给定的n生成所有可能的平方二进制矩阵，使得：对于每个二进制矩阵：1）行的总数最多为1 2）列的总数最多为1示例：n = 2，...

Answer 1

您可以考虑使用递归解决方案。考虑生成所有此类nxn矩阵。首先生成第一行：它在某个位置具有1或全为零。对于第一种情况，生成所有可能的（n-1）x（n-1）矩阵，然后对于每个列位置和每个较小的矩阵，通过在顶部插入新行来生成nxn矩阵。例如，如果您有子矩阵

Answer 2

这是解决问题的一种方法。首先，我们认识到您所需的任何矩阵实际上都是单位矩阵的行排列。因此，我们只需要生成n行的所有可能置换，并将每个置换应用于单位矩阵即可。生成排列的一种方法是使用Heap算法。下面的代码是从geeksforgeeks进行了一些修改而毫不掩饰的。

Answer 3

这是另一种基于O(n^2)使用itertools.permutations空间生成所有此类矩阵的方法：