nビットのグレイコードをバックトラッキングで生成する方法【C++実装例】

この記事では、バックトラッキングの考え方を応用して、nビットのグレイコードを生成する方法を解説します。

グレイコード（Gray Code）とは、0から 2ⁿ − 1 までの各数値をビットパターンで表した際、隣接するパターン同士が必ず1ビットだけ異なるという性質を持つ符号体系です。デジタル回路設計や誤り検出など、さまざまな分野で活用されています。

たとえば n = 2 の場合、グレイコードは (00, 01, 11, 10) となり、これらを10進数に変換すると (0, 1, 3, 2) に相当します。本プログラムでは、生成されたグレイコードの10進数表現を出力します。

アルゴリズム

再帰関数 generateGray を用いて、次の手順でグレイコードを構築します。

generateGray(arr, n, num)

begin
    if n = 0, then
        insert num into arr
        return
    end if
    generateGray(arr, n-1, num)
    num := num XOR (1 bit left shift of n-1)
    generateGray(arr, n-1, num)
end

処理のポイント

• n が 0 になった時点で、現在の num の値を結果配列 arr に格納します。
• まず n−1 ビット分のグレイコードを再帰的に生成します（前半部分）。
• 続いて num に対して「(n−1) ビット左シフトした値」とのXOR演算を施し、該当するビットを反転させます。
• 反転後の num で再度 n−1 ビット分のコードを生成します（後半部分）。

この仕組みにより、後半は前半の鏡像のような対称パターンとなり、隣接する値が必ず1ビットだけ異なるというグレイコードの性質が保たれます。

C++による実装例

#include<iostream>
#include<vector>
using namespace std;

void generateGray(vector<int>& arr, int n, int &num){
    if(n == 0){
        arr.push_back(num);
        return;
    }
    generateGray(arr, n-1, num);
    num = num ^ (1 << (n-1));
    generateGray(arr, n-1, num);
}

vector<int> gray(int n){
    vector<int> arr;
    int num = 0;
    generateGray(arr, n, num);
    return arr;
}

int main() {
    int n;
    cout << "Enter number of bits: ";
    cin >> n;
    vector<int> grayCode = gray(n);
    for(int i = 0; i < grayCode.size(); i++){
        cout << grayCode[i] << endl;
    }
}

実行結果

入力として n = 3 を与えた場合の出力は以下の通りです。

Enter number of bits: 3
0
1
3
2
6
7
5
4

出力された数列 (0, 1, 3, 2, 6, 7, 5, 4) を2進数で表すと (000, 001, 011, 010, 110, 111, 101, 100) となり、隣り合う値どうしが正しく1ビットだけ異なっていることが確認できます。計算量は要素数に比例する O(2ⁿ) であり、すべてのグレイコードを漏れなく生成できる効率的な手法です。