python - Python 中生成列和行总和小于 2 的所有 6x6 (0,1) 矩阵的最有效算法？

Question

我正在解决一个问题，该问题要求我找到具有某些给定属性的所有 6x6 (0,1) 矩阵:

• 一行/列的总和必须小于2。
• 矩阵不对称。

我正在使用这段代码:

import numpy as np
import itertools as it

n=6
li=[]

for i in it.product([0, 1], repeat = n**2):

  if (np.reshape(np.array(i), (n, n)).sum(axis=1)  < 2).all() and (np.reshape(np.array(i), (n, n)).sum(axis=0)< 2).all() :
    if (np.transpose(np.reshape(np.array(i), (n, n))) != np.reshape(np.array(i), (n, n))).any():

      li.append(np.reshape(np.array(i), (n, n)))

问题是这个方法必须遍历所有 68719476736 (0,1) 个矩阵。在这段代码之后，我仍然需要施加额外的条件。

是否有更快的算法来找到这个矩阵列表？

编辑:我正在研究的问题是找到某个等价类的唯一邻接矩阵(图论)。例如，在问题的 4x4 版本中，我想找到所有 (0,1) 矩阵:

• 某行/列的和小于2；
• 不对称，即 A^T != A;
• 还有 A^T != P^T A P，其中 P 是二面角群 D8(8 阶)的矩阵表示，它是 S4 的一个子群。

在这最后一步之后，我得到了一定数量的矩阵。如果 A 通过关系 B = P^T A P 与 B 相关，则它表示相同的矩阵。我遵循只选择这个等价类的一个代表。

在 4x4 问题中，我从 65536 变为 3。

我对第一个条件(和)排序后的结果的估计是 46080。在 6x6 问题中，转换组 P 的阶数为 48。

Answer 1

你的数学有问题，因为如果行/列的总和小于 2，它可能是 0 或 1 -- 这意味着在每一行中/column 只能是一个非零元素，即 7^6 = 117649 可能的矩阵。

100k 矩阵几乎可以通过使用蛮力来实现，并使用额外的过滤来消除垂直/水平翻转和对角线对称。

这里有一段简单的代码可以帮助您入门:

import numpy as np
from itertools import permutations

for perm in permutations( range(7), 6 ) :  # there are only 5040 permutations
    m = np.zeros(6, 6)        # start with an empty matrix
    for i, j in enumerate(perm) :
        if j == 6 : continue  # all zeros
        m[i][j] = 1           # put `1` in the current (i)-th row, (j) pos

        # here you check `m` for symmetry and save it somewhere or not