การสร้าง n-bit Gray Codes แบบ Backtracking

ในส่วนนี้เราจะดูวิธาสร้าง Gray Codes ของ n บิตด้วยแนวคิด Backtracking n-bit Gray code คือรูปแบบบิตจาก 0 ถึง 2ⁿ-1 ที่รูปแบบติดกันต่างกันแค่ 1 บิต เช่น n=2 Gray codes คือ (00, 01, 11, 10) เทียบเท่าทศนิยม (0, 1, 3, 2) โปรแกรมจะแสดงค่าทศนิยมของ Gray code

อัลกอริทึม

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

ตัวอย่างโค้ด (C++)

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

void generateGray(vector& 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 gray(int n) {
    vector arr;
    int num = 0;
    generateGray(arr, n, num);
    return arr;
}

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

ผลลัพธ์

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