अवधारणा
लंबाई m की दी गई स्ट्रिंग के संबंध में केवल लोअरकेस अक्षर होते हैं, स्ट्रिंग के n-वें क्रमपरिवर्तन को लेक्सिकोग्राफ़िक रूप से निर्धारित करना हमारा कार्य है।
इनपुट
str[] = "pqr", n = 3
आउटपुट
Result = "qpr"
स्पष्टीकरण
क्रमबद्ध क्रम में सभी संभावित क्रमपरिवर्तन - pqr, prq, qpr, qrp, rpq, rqp
इनपुट
str[] = "xyx", n = 2
आउटपुट
Result = "xyx"
स्पष्टीकरण
क्रमबद्ध क्रम में सभी संभावित क्रमपरिवर्तन - xy, xyx, yxx
विधि
यहाँ हम इस समस्या को हल करने के लिए कुछ गणितीय अवधारणा का उपयोग करते हैं।
अवधारणा निम्नलिखित तथ्यों पर आधारित है।
-
यहाँ, N वर्णों (सभी विशिष्ट) द्वारा उत्पन्न एक स्ट्रिंग के क्रमपरिवर्तन की कुल संख्या N है!
-
अब, N वर्णों द्वारा उत्पन्न एक स्ट्रिंग के क्रमपरिवर्तन की कुल संख्या (इस मामले में वर्ण C1 की आवृत्ति M1 है, C2 M2 है… और इसलिए वर्ण Ck की आवृत्ति Mk है) N!/(M1! * M2! *….एमके!)।
-
फिर से, फिक्सिंग के बाद N वर्णों (सभी विशिष्ट) द्वारा उत्पन्न स्ट्रिंग के क्रमपरिवर्तन की कुल संख्या
समाधान तक पहुंचने के लिए नीचे दिए गए चरणों का पालन किया जा सकता है।
-
सबसे पहले, हम एक सरणी freq[] में सभी वर्णों की आवृत्तियों की गणना करते हैं।
-
वर्तमान में स्ट्रिंग में मौजूद पहले सबसे छोटे वर्ण से (सबसे छोटी अनुक्रमणिका i जैसे कि
-
freq[i]> 0), हम उस विशेष i-वें वर्ण को प्रथम वर्ण मानकर संभव अधिकतम क्रमपरिवर्तन की संख्या की गणना करते हैं।
-
यह देखा गया है कि यदि यह योग मान दिए गए n से अधिक है, तो उसके बाद हम उस वर्ण को पहले परिणाम आउटपुट वर्ण, कमी freq[i] के रूप में सेट करते हैं, और बाकी n-1 वर्णों के लिए इसे जारी रखते हैं।
-
यह देखा गया है कि, दूसरी ओर, यदि गिनती आवश्यक n से छोटी है, तो आवृत्ति तालिका में अगले वर्ण के लिए पुनरावृति करें और गिनती को बार-बार संशोधित करें जब तक कि हम एक ऐसा वर्ण निर्धारित न करें जो इससे अधिक गिनती उत्पन्न करता है आवश्यक n.
यह ध्यान दिया जाना चाहिए कि उपर्युक्त विधि की समय जटिलता ओ (एन) यानी स्ट्रिंग लंबाई का क्रम है।
उदाहरण
// C++ program to print
// n-th permutation
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int MAX_CHAR1 = 26;
const int MAX_FACT1 = 20;
ll fact1[MAX_FACT1];
// Shows utility for calculating factorials
void precomputeFactorials(){
fact1[0] = 1;
for (int i = 1; i < MAX_FACT1; i++)
fact1[i] = fact1[i - 1] * i;
}
// Shows function for nth permutation
void nPermute(char str1[], int n1){
precomputeFactorials();
// Indicates length of given string
int len1 = strlen(str1);
// Used to count frequencies of all
// characters
int freq1[MAX_CHAR1] = { 0 };
for (int i = 0; i < len1; i++)
freq1[str1[i] - 'a']++;
// Shows out1 string for output string
char out1[MAX_CHAR1];
//Used to iterate till sum equals n1
int sum1 = 0;
int k1 = 0;
// We umodify both n1 and sum1 in this
// loop.
while (sum1 != n1) {
sum1 = 0;
// Verify for characters present in freq1[]
for (int i = 0; i < MAX_CHAR1; i++) {
if (freq1[i] == 0)
continue;
// Remove character
freq1[i]--;
// Compute sum1 after fixing
// a particuar char
int xsum1 = fact1[len1 - 1 - k1];
for (int j = 0; j < MAX_CHAR1; j++)
xsum1 /= fact1[freq1[j]];
sum1 += xsum1;
// Now if sum1 > n1 fix that char as
// present char and modify sum1
// and required nth after fixing
// char at that position
if (sum1 >= n1) {
out1[k1++] = i + 'a';
n1 -= (sum1 - xsum1);
break;
}
// Now if sum1 < n1, add character back
if (sum1 < n1)
freq1[i]++;
}
}
// Now if sum1 == n1 means this
// char will provide its
// greatest permutation
// as nth permutation
for (int i = MAX_CHAR1 - 1;
k1 < len1 && i >= 0; i--)
if (freq1[i]) {
out1[k1++] = i + 'a';
freq1[i++]--;
}
// Used to append string termination
// character and print result
out1[k1] = '\0';
cout << out1;
}
// Driver program
int main(){
int n1 = 5;
char str1[] = "tutorialspoint";
// int n1 = 3;
// char str1[] = "pqr";
//int n1 = 2;
//char str1[] = "xyx";
nPermute(str1, n1);
return 0;
} आउटपुट
aiilnooprtsttu