c++ - 生成超立方体链接数据

Question

我正在尝试获得一个生成超立方体链接数据的简单方法(可能是脚本或 C++ 片段)，即给定一个顶点编号为 1、...、2 的 n 维超立方体ⁿ，它产生输出:

1 3
1 5
2 3
...

其中每一行代表两个顶点之间的连接。 ( related question )

但在某种程度上不同的上下文中。我希望有人已经这样做了。输入应该是超立方体维度。提醒您，存在链接两个节点之间当且仅当它们的节点 ID 在恰好一位位置上不同时。我的意图是使用 XOR 运算符，并且当结果可以表示为 2^k 对于某些 k 时，位表示在单个位置不同，我写了一个链接。但是，我不确定如何实现它(C++ 或脚本)。

Answer 1

这是一个简短的自包含 C++ 版本，它打印 n 维超立方体的连接顶点:

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));
  }
  std::cout << '\n';
}

当 n 为 3 时的示例输出(假设您可以接受从 0 而不是 1 开始的顶点):

0: 1 2 4
1: 0 3 5
2: 3 0 6
3: 2 1 7
4: 5 6 0
5: 4 7 1
6: 7 4 2
7: 6 5 3