对于每个长度为 n+h-1 且值从 0 到 1 的数组,我想检查是否存在另一个长度为 n 且值从 -1,0,1 开始的非零数组,以便所有的 h内积为零。我的天真方法是
import numpy as np
import itertools
(n,h)= 4,3
for longtuple in itertools.product([0,1], repeat = n+h-1):
bad = 0
for v in itertools.product([-1,0,1], repeat = n):
if not any(v):
continue
if (not np.correlate(v, longtuple, 'valid').any()):
bad = 1
break
if (bad == 0):
print "Good"
print longtuple
如果我们设置 n = 19
这会很慢和 h = 10
这是我想测试的。
My goal is to find a single "Good" array of length
n+h-1
. Is there a way to speed this up so thatn = 19
andh = 10
is feasible?
当前的幼稚方法需要 2^(n+h-1)3^(n) 次迭代,每次迭代大约需要 n 次。即 n = 19
的 311,992,186,885,373,952 次迭代和 h = 10
这是不可能的。
注释 1 已更改 convolve
至correlate
以便代码考虑 v
正确的方式。
2015 年 7 月 10 日
问题仍然存在,没有足够快的解决方案 n=19
和 h=10
还没给。
最佳答案
考虑以下“在中间相遇”的方法。
首先,将 leekaiinthesky 提供的矩阵公式中的情况重铸。
接下来,请注意,我们只需要考虑 {0,1}^n
形式的“短”向量 s
(即,短向量仅包含 0 和1's) 如果我们将问题更改为找到 0 和 1 的 h x n
Hankel matrix H
使得 Hs1
永远不等于 Hs2
用于 0 和 1 的两个不同的短向量。这是因为 Hs1 = Hs2
意味着 H(s1-s2)=0
这意味着存在一个由 1、0 和 -1 组成的向量 v
,即s1-s2
,使得Hv = 0
;反之,如果 Hv = 0
for v
in {-1,0,1}^n
,那么我们可以找到s1
和 s2
在 {0,1}^n
使得 v = s1 - s2
所以 Hs1 = Hs2
.
当n=19
时,{0,1}^n
中只有524,288个向量s
可以尝试;对结果 Hs
进行哈希处理,如果相同的结果出现两次,则 H
不好,然后尝试另一个 H
。就内存而言,这种方法是相当可行的。有2^(n+h-1)
汉克尔矩阵H
可以试试;当 n=19
和 h=10
是 268,435,456 个矩阵。那是 2^38
测试,或 274,877,906,944,每个测试都有大约 nh
操作来将矩阵 H
和向量 s
相乘>,大约 52 万亿次操作。这似乎可行,不是吗?
由于您现在只处理 0 和 1,而不是 -1,因此您还可以通过使用位操作(移位和计数 1)来加快处理速度。
更新
我用 C++ 实现了我的想法。我使用位运算来计算点积,将结果向量编码为长整数,并使用 unordered_set 检测重复项,当发现点积的重复向量时,提前退出给定的长向量。
几分钟后,我获得了 n=17 和 h=10 的 00000000010010111000100100 和几分钟后获得了 n=18 和 h=10 的 000000111011110001001101011 。我正要运行它 n=19 和 h=10。
#include <iostream>
#include <bitset>
#include <unordered_set>
/* Count the number of 1 bits in 32 bit int x in 21 instructions.
* From /Hackers Delight/ by Henry S. Warren, Jr., 5-2
*/
int count1Bits(int x) {
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x0000003F;
}
int main () {
const int n = 19;
const int h = 10;
std::unordered_set<long> dotProductSet;
// look at all 2^(n+h-1) possibilities for longVec
// upper n bits cannot be all 0 so we can start with 1 in pos h
for (int longVec = (1 << (h-1)); longVec < (1 << (n+h-1)); ++longVec) {
dotProductSet.clear();
bool good = true;
// now look at all n digit non-zero shortVecs
for (int shortVec = 1; shortVec < (1 << n); ++shortVec) {
// longVec dot products with shifted shortVecs generates h results
// each between 0 and n inclusive, can encode as h digit number in
// base n+1, up to (n+1)^h = 20^10 approx 13 digits, need long
long dotProduct = 0;
// encode h dot products of shifted shortVec with longVec
// as base n+1 integer
for(int startShort = 0; startShort < h; ++startShort) {
int shortVecShifted = shortVec << startShort;
dotProduct *= n+1;
dotProduct += count1Bits(longVec & shortVecShifted);
}
auto ret = dotProductSet.insert(dotProduct);
if (!ret.second) {
good = false;
break;
}
}
if (good) {
std::cout << std::bitset<(n+h-1)>(longVec) << std::endl;
break;
}
}
return 0;
}
第二次更新
n=19 和 h=10 的程序在我的笔记本电脑的后台运行了两周。最后,它只是退出而没有打印任何结果。除非程序中出现某种错误,否则看起来没有具有您想要的属性的长向量。我建议寻找为什么没有这么长的向量的理论原因。也许某种计数论点会起作用。
关于python - 快速找到全零答案的方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30262104/