我正在尝试为给定的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,...
您可以考虑使用递归解决方案。考虑生成所有此类nxn矩阵。首先生成第一行:它在某个位置具有1或全为零。对于第一种情况,生成所有可能的(n-1)x(n-1)矩阵,然后对于每个列位置和每个较小的矩阵,通过在顶部插入新行来生成nxn矩阵。例如,如果您有子矩阵
这是解决问题的一种方法。首先,我们认识到您所需的任何矩阵实际上都是单位矩阵的行排列。因此,我们只需要生成n行的所有可能置换,并将每个置换应用于单位矩阵即可。生成排列的一种方法是使用Heap算法。下面的代码是从geeksforgeeks进行了一些修改而毫不掩饰的。
这是另一种基于O(n^2)
使用itertools.permutations
空间生成所有此类矩阵的方法: