python - 具有某些属性的所有可能的二进制矩阵

Question

我需要生成所有可能的 4x4 二进制矩阵，这些矩阵在主对角线上有零，是对称的，并且有六个条目等于 1。一些例子：

[[0,0,0,0],
 [0,0,1,1],
 [0,1,0,1],
 [0,1,1,0]],

[[0,1,1,0],
 [1,0,1,0],
 [1,1,0,0],
 [0,0,0,0]],  

[[0,1,0,1],
 [1,0,0,1],
 [0,0,0,0],
 [1,1,0,0]]

我怎么能在 Python 中做到这一点？

Answer 1

这相当于选择对角线上方的六个条目中的哪三个是 1。

从 4 x 4 矩阵中的对角线以上位置列表：

sage: positions = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

使用 Sage'sSubsets获取这些位置的所有大小为 3 的子集。

sage: S = Subsets([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)], 3)

然后构建相应的矩阵。

sage: [matrix(ZZ, 4, lambda i, j: (i, j) in s or (j, i) in s) for s in S]
[
[0 1 1 1]  [0 1 1 0]  [0 1 1 0]  [0 1 1 0]  [0 1 0 1]  [0 1 0 1]
[1 0 0 0]  [1 0 1 0]  [1 0 0 1]  [1 0 0 0]  [1 0 1 0]  [1 0 0 1]
[1 0 0 0]  [1 1 0 0]  [1 0 0 0]  [1 0 0 1]  [0 1 0 0]  [0 0 0 0]
[1 0 0 0], [0 0 0 0], [0 1 0 0], [0 0 1 0], [1 0 0 0], [1 1 0 0],

[0 1 0 1]  [0 1 0 0]  [0 1 0 0]  [0 1 0 0]  [0 0 1 1]  [0 0 1 1]
[1 0 0 0]  [1 0 1 1]  [1 0 1 0]  [1 0 0 1]  [0 0 1 0]  [0 0 0 1]
[0 0 0 1]  [0 1 0 0]  [0 1 0 1]  [0 0 0 1]  [1 1 0 0]  [1 0 0 0]
[1 0 1 0], [0 1 0 0], [0 0 1 0], [0 1 1 0], [1 0 0 0], [1 1 0 0],

[0 0 1 1]  [0 0 1 0]  [0 0 1 0]  [0 0 1 0]  [0 0 0 1]  [0 0 0 1]
[0 0 0 0]  [0 0 1 1]  [0 0 1 0]  [0 0 0 1]  [0 0 1 1]  [0 0 1 0]
[1 0 0 1]  [1 1 0 0]  [1 1 0 1]  [1 0 0 1]  [0 1 0 0]  [0 1 0 1]
[1 0 1 0], [0 1 0 0], [0 0 1 0], [0 1 1 0], [1 1 0 0], [1 0 1 0],

[0 0 0 1]  [0 0 0 0]
[0 0 0 1]  [0 0 1 1]
[0 0 0 1]  [0 1 0 1]
[1 1 1 0], [0 1 1 0]
]

请注意，这些是在四个标记的顶点上具有三个边的所有图的邻接矩阵。

如果您想要未标记的顶点，或者等效地想要在四个顶点上具有三个边的图的等价类的邻接矩阵列表，您可以使用 Nauty 来枚举它们。以下是 Sage 的方法：

sage: G = graphs.nauty_geng("4 3:3")
sage: G
<generator object nauty_geng at 0x21c89a0f0>
sage: [g.adjacency_matrix() for g in G]
[
[0 0 0 1]  [0 0 1 1]  [0 0 1 1]
[0 0 0 1]  [0 0 0 1]  [0 0 0 0]
[0 0 0 1]  [1 0 0 0]  [1 0 0 1]
[1 1 1 0], [1 1 0 0], [1 0 1 0]
]