Hoán vị vòng trong biểu diễn nhị phân (Gray Code) trong C++

Mô tả bài toán

Cho n và start. Tìm hoán vị p của [0, 1, ..., 2^n - 1] sao cho:

• p[0] = start.
• Các phần tử liên tiếp khác nhau đúng 1 bit (Gray code).
• p[0] và p[2^n-1] cũng khác 1 bit.

Ví dụ: n=2, start=3 → [3,2,0,1] (nhị phân: 11,10,00,01).

Giải thuật

Gray code chuẩn: g(i) = i ^ (i >> 1). Hoán vị bắt đầu từ start là: p[i] = start ^ g(i).

Chứng minh: g(i) và g(i+1) khác 1 bit ⇒ start ^ g(i) và start ^ g(i+1) cũng khác 1 bit. Và g(0)=0, g(2^n-1)=2^(n-1) khác 1 bit với 0.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> v) {
    cout << "[";
    for (int x : v) cout << x << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> circularPermutation(int n, int start) {
        vector<int> ans;
        ans.reserve(1 << n);
        for (int i = 0; i < (1 << n); i++) {
            ans.push_back(start ^ i ^ (i >> 1));
        }
        return ans;
    }
};

int main() {
    Solution ob;
    print_vector(ob.circularPermutation(5, 3));
    return 0;
}

Độ phức tạp

• Thời gian: O(2^n) (phải sinh ra tất cả phần tử).
• Không gian: O(2^n) cho mảng kết quả.