您可以将此归类为“好过没有”;-) 这是一个纯Python3代码,它重新思考了这个问题。也许numpy技巧可以极大地加速它,但难以看出如何做到这一点。
- 这里的“一行”是
range(2**n)
中的整数。因此,数组只是由整数组成的元组。
- 因此,通过
combinations_with_replacement()
轻松生成所有在行置换下唯一的数组。这将外部循环的旅行次数从2**(n**2)
减少到(2**n+n-1)-choose-n)
。这是一个巨大的减少,但仍然...
- 预计算的字典将行对(这意味着这里是整数对!)映射到它们的向量和作为元组。因此,在测试时不需要进行任何数组操作,除了测试元组是否相等。通过一些更巧妙的方法,元组可以编码为(比如)基于3的整数,将内层循环测试减少到从一对字典查找检索的两个整数之间进行比较。
- 用于预计算的时间和空间是相对微不足道的,因此没有尝试加速该部分。
- 内循环每次选择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找到结果了,虽然最后一个结果需要很长时间才能完成(具体多久不知道-没有计时 - 大约需要一小时左右,“很长时间”是相对的;-)):
>>> count(4)
3136
>>> count(5)
3053312
>>> count(6)
7247819776
编辑 - 删除了一些不必要的索引
通过将主函数更改为以下内容,可以获得较快的速度:
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
for a in cwr(range(2**n), n):
for r0, r1, r2, r3 in combinations(a, 4):
if rowpair2sum[r0, r1] == rowpair2sum[r2, r3] or \
rowpair2sum[r0, r2] == rowpair2sum[r1, r3] or \
rowpair2sum[r0, r3] == rowpair2sum[r1, r2]:
total += multinomial(n, Counter(a).values())
break
return total
编辑 - 加快求和测试速度
虽然这只是个小问题,但由于目前似乎这是最精确的方法之一,因此可以尝试提高一些性能。 正如之前所指出的,由于每个和都在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能够获得更多的好处。