Permutation Sequence - หาลำดับการเรียงสับที่ k ใน C++

ภาพรวมปัญหา

ชุด [1,2,3,...,n] มี n! การเรียงสับ (permutations) เรียงตามลำดับ หาลำดับที่ k (1-indexed)

n ∈ [1,9], k ∈ [1, n!]

ตัวอย่าง

n=3: ["123","132","213","231","312","321"]
k=4 → "231"

อัลกอริทึม (Mathematical / Factorial Number System)

1. สร้าง candidates = ['1','2',...,'n']
2. คำนวณ factorial ล่วงหน้า fact[0..n]
3. k-- (แปลงเป็น 0-indexed)
4. for i = n-1 ถึง 0:
   • idx = k / fact[i]
   • ans += candidates[idx]
   • ลบ candidates[idx] ออก (shift ซ้าย)
   • k = k % fact[i]
5. return ans

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

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

class Solution {
public:
    string getPermutation(int n, int k) {
        string ans = "";
        vector <char> candidates(n);
        for(lli i = 0; i < n; i++) candidates[i] = ((i + 1) + '0');
        vector <lli> fact(n + 1);
        fact[0] = 1;
        for(lli i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
        k--;
        for(lli i = n - 1; i >= 0; i--){
            lli idx = k / fact[i];
            ans += candidates[idx];
            for(lli j = idx; j + 1 < candidates.size(); j++)
                candidates[j] = candidates[j + 1];
            k = k % fact[i];
        }
        return ans;
    }
};

int main(){
    Solution ob;
    cout << ob.getPermutation(4, 9);
}

Input / Output

Input:  4 9
Output: 2314