การเรียงสับเปลี่ยนแบบวงกลมในรูปแบบไบนารีใน C++

ให้จำนวนเต็ม n และ start ต้องการสร้างการเรียงสับเปลี่ยน p ของ 0,1,2,...,2^n-1 ที่สอดคล้องเงื่อนไข:

• p[0] = start
• p[i] และ p[i+1] แตกต่างกันเพียง 1 บิตในรูปแบบไบนารี
• p[0] และ p[2^n-1] ก็ต้องแตกต่างกัน 1 บิตเช่นกัน

นี่คือ Gray Code ที่หมุนเริ่มต้นที่ start ตัวอย่าง: n=2, start=3 → [3,2,0,1] (ไบนารี: 11, 10, 00, 01)

ขั้นตอนการแก้ปัญหา

1. สร้างอาร์เรย์ ans
2. วน i จาก 0 ถึง 2^n - 1 ใส่ start ^ i ^ (i >> 1) เข้า ans
3. คืน ans

สูตร i ^ (i >> 1) คือ Gray Code มาตรฐาน การ XOR กับ start จะหมุนลำดับให้เริ่มที่ start

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

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

void print_vector(vector<int> 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;
    }
};

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

Input

5 3

Output

[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, ]