超立方体生成数据链接 [英] Generating hypercube links data

问题描述

我试图得到一个简单的方法（脚本或C ++代码片段，也许）生成一个超立方体链路数据，也就是说，给出一个n维超立方体与顶点编号为1，...，2 ^N ，它产生的输出：

I'm trying to get a simple method (a script or a c++ snippet, perhaps) that generates a hypercube links data, i.e., given an n-dimensional hypercube with vertices numbered as 1, ..., 2ⁿ, it produces the output:

1 3
1 5
2 3
...

每行再presents两个顶点之间的连接。 （相关的问题）

但在有些不同的上下文。我希望有人已经做到了这一点。输入应该是超立方体的维度。要提醒大家，存在链接
两个节点之间，当且仅当它们的节点内径在正好一个位位置不同。
我的目的是使用XOR运算符，当结果可能是前pressed为2 ^K 对某个k，那么该位再presentations在一个单一的位置不同，而我写的一条链接。但是，我不知道如何得到这个实现的（C ++或脚本）。

But in a somehow different context. I hope someone has already done this. The input should be the hypercube dimensionality. To remind you, links exist between two nodes if and only if their node i.d.'s differ in exactly one bit position. My intention was to use XOR operator, and when the result can be expressed as 2^k for some k, then the bit representations differ in a single position, and I write a link. However, I'm not sure how to get this implemented (C++ or script).

推荐答案

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

Here's a short, self-contained C++ version that prints the connected vertices for an n-dimensional hypercube:

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）：

Example output when n is 3 (assuming you're okay with vertices that start at 0, not 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

这篇关于超立方体生成数据链接的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！