C++-এ পারমুটেশন সিকোয়েন্স (k-তম পারমুটেশন বের করা)

সেট [1,2,3,...,n]-এর মোট n!টি ইউনিক পারমুটেশন থাকে। সেগুলো ক্রম অনুযায়ী লিস্ট করলে n=3 হলে: ["123","132","213","231","312","321"]। n এবং k দেওয়া থাকলে k-তম পারমুটেশন রিটার্ন করতে হবে। n: 1-৯, k: 1-n!।

সমাধান: ফ্যাক্টোরিয়াল অ্যারে বানিয়ে k-১ করে প্রতিটি পজিশনে কোন ডিজিট আসবে তা ক্যালকুলেট করব। ক্যান্ডিডেট অ্যারে থেকে ডিজিট বেছে নিলে সেটি রিমুভ করব।

উদাহরণ

#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;
    }
};

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

ইনপুট

4 9

আউটপুট

2314