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

Question

^{我正在尝试获得一个生成超立方体链接数据的简单方法（可能是脚本或 c++ 片段），即，给定一个顶点编号为 1, ..., 2 n}的 n 维超立方体，它会产生输出：

其中每一行代表两个顶点之间的连接。（相关问题）

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

score 2 · Accepted Answer

C++ 中的蛮力方法 O(2^(2k))：

int n = 32 // or any other power of 2
for(int i = 0; i < n; i++){
   // we check with which vertices is it connected
   for(int j = 0; j < i; j++){
     // we stop when j >= i, because we want to output each unordered pair once
     int u = i ^ j;

     // we check if U is a power of 2, by rounding it up to next power of two and
     // checking if it changed
     int k = u - 1;
     k |= k >> 1;
     k |= k >> 2;
     k |= k >> 4;
     k |= k >> 8;
     k |= k >> 16;

     if(k + 1 == u)
       cout << i << " " << j << endl;
   } 
}

如果您需要更快的解决方案，我建议您尝试递归，因为超立方体的结构本身就是递归的：n 维超立方体由两个 n-1 维超立方体组成，它们仅在一个坐标上不同。以一个正方形为例 - 它由两个在一个坐标上不同的段（一维）组成。

递归解决方案的算法将或多或少像这样（python）：

# outputs pair (list of vertices, list of connections beetween them), for n
# dimensional hypercube with vertices starting at x
def hypercube(n, i):
  if n == 1:
    return (i, [])
  v1, e1 = hypercube(n-1, i)
  v2, e2 = hypercube(n-1, i + len(v1))
  return(v1 + v2, zip(v1, v2) + e1 + e2)

score 2 · Accepted Answer

这是一个简短的、独立的 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）：

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

2 回答 2

Related

Reference