C++でのバイナリ表現の循環順列：グレイコードによる効率的な実装

問題の概要

2つの整数 n と start が与えられたとき、0 から 2^n − 1 までの整数の順列 p を、以下の条件を満たすように求める問題を考えます。

• p[0] = start であること
• 隣接する要素 p[i] と p[i+1] の2進数（バイナリ）表現は、1ビットのみ異なること
• 最初と最後の要素である p[0] と p[2^n − 1] も、1ビットのみ異なること

たとえば、n = 2、start = 3 が入力された場合、答えは [3, 2, 0, 1] となります。これを2進数で表すと [11, 10, 00, 01] であり、隣り合う値同士（最後の要素と最初の要素を含む）が必ず1ビットだけ異なっていることが確認できます。

解法のアプローチ：グレイコードの活用

この問題を効率的に解く鍵となるのがグレイコード（Gray code）です。グレイコードとは、隣接する数値の2進表現が必ず1ビットしか異ならないように並べた数列のことです。

n ビットのグレイコードは、次のシンプルな式で生成できます。

g(i) = i XOR (i >> 1)

さらに、このグレイコード全体に start をXOR演算で適用することで、任意の値から始まる循環順列が得られます。XORの性質により、「隣接要素が1ビット違い」という性質は保たれたまま、最初の要素が必ず start になります。

アルゴリズムの手順

1. 結果を格納する配列 ans を用意する
2. i を 0 から 2^n − 1 まで繰り返し、ans に「start XOR i XOR (i / 2)」を挿入する
3. ans を返す

C++での実装例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
public:
    vector<int> circularPermutation(int n, int start) {
        vector <int> ans;
        for(int i = 0 ; i < 1<<n; i++){
            ans.push_back(start ^ i ^(i>>1));
        }
        return ans;
    }
};
main(){
    Solution ob;
    print_vector(ob.circularPermutation(5,3));
}

入力

5
3

出力

[3, 2, 0, 1, 5, 4, 6, 7, 15, 14, 12, 13, 9, 8, 10, 11, 27, 26, 24, 25, 29, 28,
30, 31, 23, 22, 20, 21, 17, 16, 18, 19]

計算量の評価

このアルゴリズムは 0 から 2^n − 1 までの各値を一度ずつ処理するため、時間計算量は O(2^n)、結果を格納するための空間計算量も O(2^n) となります。ビット演算のみで構成されているためオーバーヘッドが極めて小さく、n = 20 程度の規模でも実用的な速度で動作する点が大きなメリットです。