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

Question

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

换句话说，上面的答案给了我们 hypercube graph 的所有边.用这些术语来说，我正在寻找一种有效的方法来生成 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';
}