3

ハイパーキューブ リンク データを生成する単純なメソッド(おそらくスクリプトまたは C++ スニペット) を取得しようとしています。出力：

1 3
1 5
2 3
...

各行は 2 つの頂点間の接続を表します。(関連質問)

しかし、どういうわけか異なる文脈で。誰かがすでにこれを行っていることを願っています。入力はハイパーキューブの次元でなければなりません。2 つのノード間にリンクが存在するのは、それらのノード ID が正確に 1 ビット位置で異なる場合のみです。私の意図は XOR 演算子を使用することでした。結果が 2 kの k で表現できる場合、ビット表現は 1 つの位置で異なり、リンクを書きます。ただし、これを実装する方法がわかりません (C++ またはスクリプト)。

4

2 に答える 2

2

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 次元のハイパーキューブは、1 つの座標のみが異なる 2 つの n-1 次元のハイパーキューブから作成されます。正方形を例にとると、正確に 1 つの座標が異なる 2 つのセグメント (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)
于 2012-06-06T11:15:45.927 に答える
2

以下は、n 次元のハイパーキューブの接続された頂点を出力する、自己完結型の短い C++ バージョンです。

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 の場合の出力例 (1 ではなく 0 から始まる頂点で問題ないと仮定):

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
于 2012-06-06T11:58:48.447 に答える