ধরুন সেটটি [1,2,3,...,n] এর মত, মোট n রয়েছে! অনন্য স্থানান্তর। ক্রমানুসারে সমস্ত পারমুটেশনের তালিকা এবং লেবেল করার মাধ্যমে, আমরা n =3 এর জন্য এই ক্রমটি পাই:["123","132","213","231","312","321"] তাই যদি n এবং k দেওয়া হয়, তারপর kth পারমিউটেশন ক্রম ফেরত দিন। n হবে 1 থেকে 9 (অন্তর্ভুক্ত) এবং k হবে 1 থেকে n এর মধ্যে! (অন্তর্ভুক্ত). উদাহরণস্বরূপ যদি n =3.
আসুন ধাপগুলো দেখি -
- উত্তর :=খালি স্ট্রিং, n আকারের প্রার্থী বলে অ্যারেকে সংজ্ঞায়িত করুন
- আমি 0 থেকে n – 1
- পরিসরে
- প্রার্থী[i] :=((i + 1) + অক্ষর '0')
- একটি অ্যারে তৈরি করুন যার নাম ফ্যাক্ট অফ সাইজ n + 1, সেট ফ্যাক্ট[0] :=1
- আমি 1 থেকে n
- পরিসরে
- তথ্য[i] :=ঘটনা[i – 1] * i
- k কে 1 দ্বারা কমিয়ে দিন
- এর জন্য i :=n – 1 নিচে 0
- idx :=k / fact[i]
- উত্তর :=উত্তর + প্রার্থী[idx]
- j :=idx, j + 1 <প্রার্থীদের সাইজ
- এর জন্য
- প্রার্থী[j] :=প্রার্থী[j + 1]
- k :=k mod fact[i]
- উত্তর ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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
