Generating hypercube links data

Question

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

Answer 1

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