生成所有汉明距离至多为2的无序位串对

Question

我正在寻找一种有效的方法来生成汉明距离最多为 2 的所有无序位串对（表示为整数）。在 this answer 中显示了这是如何非常有效地完成的对于汉明距离为 1 的对。

换句话说，上面的答案给了我们超立方体 hypercube graph. Phrased in these terms, I'm looking for an efficient way to generate the edges of the square 的所有边。

是否有一些众所周知的快速方法，也许类似地基于位技巧？

Answer 1

对 Nate Kohl's answer 有一个简单的修改。

int n = 3;
// examine all vertices from 0...2^n-1
unsigned long long max = 1ULL << n;  
for (unsigned long long vertex = 0; vertex < max; ++vertex) {
  std::cout << vertex << ':';
  // print all vertices that differ from vertex by one bit
  unsigned long long mask = 1;
  for (int shift_amt = 0; shift_amt < n; ++shift_amt) {
    std::cout << ' ' << (vertex ^ (mask << shift_amt));
  }
  for (int shift_amt1 = 0; shift_amt1 < n; ++shift_amt1) {
    for (int shift_amt2 = 0; shift_amt2 < shift_amt1; ++shift_amt2) {
      std::cout << ' ' << (vertex ^ (mask << shift_amt1) ^ (mask << shift_amt2));
    }
  }
  std::cout << '\n';
}

生成所有汉明距离至多为2的无序位串对

Generate all unordered pairs of bit strings with Hamming distance at most 2

c++

algorithm

combinatorics

hamming-distance