找到全零答案的快速方法

Question

对于每个长度为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这是我想要测试的.

我的目标是找到一个长度单一的"好"数组n+h-1.有没有办法加快这让n = 19和h = 10是否可行？

当前的朴素方法需要2 ^(n + h-1)3 ^(n)次迭代,每次迭代大约需要n次.这是311,992,186,885,373,952次迭代n = 19,h = 10这是不可能的.

注1更改convolve为correlate以便代码v以正确的方式考虑.

---

2015年7月10日

问题是仍然没有解决足够快的开放n=19和h=10尚未给出.

Answer 1

考虑以下"中间相遇"方法.

首先,重新描述leekaiinthesky提供的矩阵公式中的情况.

接下来,注意,我们只需要考虑"短"载体s形式的{0,1}^n(即,含有短矢量只有0和1)如果我们改变问题找到一个h x n 汉克尔矩阵 H的0和1的,使得Hs1永远等于Hs2用于两个不同0和1的短向量.那是因为Hs1 = Hs2暗示H(s1-s2)=0有一个v1,0和-1的向量,即s1-s2,这样Hv = 0; 反之,如果Hv = 0对v中{-1,0,1}^n,那么我们就可以发现s1并s2在{0,1}^n这样v = s1 - s2如此Hs1 = Hs2.

当n=19只有524,288个载体s在{0,1}^n尝试时; 哈希结果Hs,如果相同的结果出现两次然后H是不好的,尝试另一个H.就记忆而言,这种方法非常可行.有2^(n+h-1)Hankel矩阵H可以尝试; 何时n=19和h=10那是268,435,456矩阵.这是2^38测试,或274,877,906,944,每个都有关于nh矩阵H和向量相乘的操作s,大约52万亿个操作.那似乎可行,不是吗？

既然你现在只处理0和1,而不是-1,你也可以通过使用位操作(shift,和,计数1)来加速这个过程.

更新

我用C++实现了我的想法.我正在使用位操作来计算点积,将结果向量编码为长整数,并使用unordered_set来检测重复项,当找到点积的复制向量时,从给定的长向量中提前退出.

我获得了00000000010010111000100100,其中n = 17,几分钟后h = 10,000000111011110001001101011,n = 18,h = 10,稍长一些.我正要为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的程序在笔记本电脑的后台运行了两周.最后,它只是退出而不打印任何结果.除非程序中出现某种错误,否则看起来没有长矢量具有您想要的属性.我建议寻找没有这么长的载体的理论原因.也许某种计数论证会起作用.

Answer 2

下面是一个将复杂度从 3^n 降低到 3^{nh} 的算法。

令 v_1, v_2, .., v_h 为您需要正交的向量。

考虑向量空间 (Z/3Z)^n。令 v'_1, .., v'_h 为该空间中 v_1, .., v_h 的自然包含体。

现在令 w 为系数为 {-1,0,1} 的向量，并令 w' 为通过自然地将 w 视为 (Z/3Z)^n 向量而获得的 (Z/3Z)^n 向量。那么 w 与 v_1, .., v_h （在 R 中）具有零标量积的必要条件是 w' 与 v'_1, .., v 具有零标量积（在 (Z/3Z)^n 中） '_H。

现在您可以很容易地确定与 v'_1, .., v'_h 具有零标量积的 w'。它们将形成一个大小为 3^{nh} 的空间。然后，您需要检查它们中的每一个，关联的 w 是否实际上与所有 v_i 正交。