Python中生成所有6x6 (0,1)矩阵的最有效算法，其中列和行和小于2？
Python中生成所有6x6 (0,1)矩阵的最有效算法，其中列和行和小于2？
提问于 2018-07-24 01:37:52
我正在解决一个问题，它要求我找到所有具有某些给定属性的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相关，则A表示相同的矩阵。接下来，我只选择这个等价类的一个代表。
在4x4的问题中，我从65536到3。
在对第一个条件(sums)进行排序后，我对结果的估计是46080。在6x6问题中，变换组P是48阶的。
回答 1
Stack Overflow用户
发布于 2018-07-24 23:30:26
您的数学有问题，因为如果行/列和小于2，它可能是0或1 --这意味着在每行/列中只能有一个非零元素，即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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/51484410
复制相关文章
相似问题