我正在解决一个问题,它要求我找到所有具有某些给定属性的6x6 (0,1)矩阵:
我使用的是以下代码:
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)矩阵,使得:
在这最后一步之后,我得到了一定数量的矩阵。如果A通过关系B= P^T A P与B相关,则A表示相同的矩阵。接下来,我只选择这个等价类的一个代表。
在4x4的问题中,我从65536到3。
在对第一个条件(sums)进行排序后,我对结果的估计是46080。在6x6问题中,变换组P是48阶的。
发布于 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
https://stackoverflow.com/questions/51484410
复制相似问题