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

问题描述

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

  1 3 
 1 5 
 2 3 
 ... 
  

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

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

解决方案

C +版本，其打印n维超立方体的连接顶点：

  int n = 3; 
 //检查所有顶点从0 ... 2 ^ n-1 
 unsigned long long max = 1ULL< n; 
 for（unsigned long long vertex = 0; vertex< max; ++ vertex）{
 std :: cout<顶点<< '：'; 
 //打印所有与顶点不同一个顶点的顶点
 unsigned long long mask = 1; 
 for（int shift_amt = 0; shift_amt< n; ++ shift_amt）{
 std :: cout< ''<< （顶点^（掩码<<< shift_amt））; 
} 
 std :: cout<< '\\\
'; 
} 
  

当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 
  

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
...

Where each row represents a connection between two vertices. (related question)

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).

解决方案

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';
}

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屋！