python - 快速找到全零答案的方法

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这是我想测试的。

My goal is to find a single "Good" array of length n+h-1. Is there a way to speed this up so that n = 19 and h = 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还没给。

Answer 1

考虑以下“在中间相遇”的方法。

首先，将 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 的程序在我的笔记本电脑的后台运行了两周。最后，它只是退出而没有打印任何结果。除非程序中出现某种错误，否则看起来没有具有您想要的属性的长向量。我建议寻找为什么没有这么长的向量的理论原因。也许某种计数论点会起作用。