मान लीजिए समूह [1,2,3,...,n] है, जिसमें कुल n! अद्वितीय क्रमचय (permutations) होते हैं। सभी क्रमचयों को क्रम में सूचीबद्ध और लेबल करने पर, n = 3 के लिए हमें यह अनुक्रम मिलता है: ["123","132","213","231","312","321"]। यदि n और k दिए गए हैं, तो k-वां क्रमचय अनुक्रम वापस करें। n 1 से 9 (सम्मिलित) के बीच होगा और k 1 से n! (सम्मिलित) के बीच होगा।
आइए चरण देखें:
- ans := खाली स्ट्रिंग, candidates नामक सरणी परिभाषित करें आकार n की
- i को 0 से n – 1 तक की रेंज में:
- candidates[i] := ((i + 1) + वर्ण '0')
- fact नामक एक सरणी बनाएं आकार n + 1 की, fact[0] := 1 सेट करें
- i को 1 से n तक की रेंज में:
- fact[i] := fact[i – 1] * i
- k को 1 घटाएं
- i := n – 1 से 0 तक डाउन करें:
- idx := k / fact[i]
- ans := ans + candidates[idx]
- j := idx से, j + 1 < candidates का आकार:
- candidates[j] := candidates[j + 1]
- k := k mod fact[i]
- ans वापस करें
उदाहरण
#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);
}
इनपुट
4 9
आउटपुट
2314