寻找一种更好的计算矩阵的方法

Question

我想计算只有1和0个条目的2d数组的向量和相等的不相交对。对于一个4乘4的矩阵，下面的代码通过迭代所有这些矩阵并依次测试每个矩阵来实现这一点。在

import numpy as np
from itertools import combinations
n = 4
nxn = np.arange(n*n).reshape(n, -1)
count = 0
for i in xrange(2**(n*n)):
   A = (i >> nxn) %2
   p = 1
   for firstpair in combinations(range(n), 2):
       for secondpair in combinations(range(n), 2):
           if firstpair < secondpair and not set(firstpair) & set(secondpair):
              if (np.array_equal(A[firstpair[0]] + A[firstpair[1]], A[secondpair[0]] + A[secondpair[1]] )):
                  if (p):
                      count +=1
                      p = 0
print count

输出是3136。在

问题是它使用2^（4^2）次迭代，我想运行它n到8次。有没有一种更聪明的方法可以在不迭代所有矩阵的情况下计算这些值？例如，反复创建同一矩阵的排列似乎毫无意义。在

Answer 1

你可以把这个放在“总比没有好”；—）这里有一个简单的Python3代码，可以稍微重新考虑一下这个问题。也许“裸体把戏”可以大大加快速度，但很难说是怎么回事。在

1. 这里的“A row”是range(2**n)中的一个整数。所以数组只是一个整数元组。在
2. 因此，通过combinations_with_replacement()生成行置换下唯一的所有数组非常容易。这会将外循环上的跳闸计数从2**(n**2)减少到{}。一个巨大的减少，但仍然。。。在
3. 预计算的dict映射成对的行（这里是指整数对！）它们的向量和作为元组。因此，测试时不需要数组操作，只需要测试元组是否相等。再加上一些技巧，元组可以被编码为（比如）base-3整数，这样就可以将内环测试简化为比较从一对dict查找中检索到的两个整数。在
4. 预计算dict所需的时间和空间相对较小，因此没有尝试加快该部分的速度。在
5. 内部循环一次选择行索引4，而不是一对循环一次选择两个索引。一次完成所有4个任务会更快，这在很大程度上是因为不需要使用重复索引剔除对。在

代码如下：

def calc_row_pairs(n):
    fmt = "0%db" % n
    rowpair2sum = dict()
    for i in range(2**n):
        row1 = list(map(int, format(i, fmt)))
        for j in range(2**n):
            row2 = map(int, format(j, fmt))
            total = tuple(a+b for a, b in zip(row1, row2))
            rowpair2sum[i, j] = total
    return rowpair2sum

def multinomial(n, ks):
    from math import factorial as f
    assert n == sum(ks)
    result = f(n)
    for k in ks:
        result //= f(k)
    return result

def count(n):
    from itertools import combinations_with_replacement as cwr
    from itertools import combinations
    from collections import Counter
    rowpair2sum = calc_row_pairs(n)
    total = 0
    class NextPlease(Exception):
        pass
    for a in cwr(range(2**n), n):
        try:
            for ix in combinations(range(n), 4):
                for ix1, ix2, ix3, ix4 in (
                       ix,
                       (ix[0], ix[2], ix[1], ix[3]),
                       (ix[0], ix[3], ix[1], ix[2])):
                    if rowpair2sum[a[ix1], a[ix2]] == \
                       rowpair2sum[a[ix3], a[ix4]]:
                        total += multinomial(n, Counter(a).values())
                        raise NextPlease
        except NextPlease:
            pass
    return total

这足以通过n=6找到结果，尽管完成最后一个需要很长时间（多长时间？不知道-没有计时-大约一个小时，尽管-“长时间”是相对的；-）：

^{pr2}$

编辑-删除一些不必要的索引

通过将主函数改为：

^{3}$

编辑-加速和测试

这是次要的，但既然这似乎是目前为止桌上最好的精确方法，那么不妨从中挤出更多。如前所述，由于每个和都在range(3)中，每个和元组都可以替换为一个整数（将元组视为给出以3为基数的整数的位数）。替换calc_row_pairs()，如下所示：

def calc_row_pairs(n):
    fmt = "0%db" % n
    rowpair2sum = dict()
    for i in range(2**n):
        row1 = list(map(int, format(i, fmt)))
        for j in range(2**n):
            row2 = map(int, format(j, fmt))
            total = 0
            for a, b in zip(row1, row2):
                t = a+b
                assert 0 <= t <= 2
                total = total * 3 + t
            rowpair2sum[i, j] = total
    return rowpair2sum

我相信numpy有一个更快的方法来做到这一点，但是calc_row_pairs()所花费的时间是微不足道的，所以为什么要费心呢？顺便说一句，这样做的好处是内部循环==测试从需要比较元组变为只比较小整数。纯Python从中受益，但我敢打赌pypy可能会受益更多。在

Answer 2

这不是对你的问题的直接回答，但正如我所说，我认为你可以放心地忘记对所有矩阵进行穷尽性测试，以确定是否有任何显著的n。但是这个问题很适合于随机特征。有趣的是，在某些情况下，三和比双和更常见！被击中的可能性似乎是n和m的一个相当简单（单调的）函数，但这并不奇怪。在

Answer 3

在我的机器上用CPython 3.3计算出：

4 3136
5 3053312
6 7247819776
7 53875134036992
8 1372451668676509696

代码，基于记忆的包含排除：

^{pr2}$