ধারণা
শুধুমাত্র ছোট হাতের বর্ণমালা সম্বলিত m দৈর্ঘ্যের একটি প্রদত্ত স্ট্রিং এর ক্ষেত্রে, আমাদের কাজ হল অভিধানিকভাবে স্ট্রিংটির n-ম স্থানান্তর নির্ধারণ করা।
ইনপুট
str[] = "pqr", n = 3
আউটপুট
Result = "qpr"
ব্যাখ্যা
সাজানো ক্রমে সমস্ত সম্ভাব্য স্থানান্তর - pqr, prq, qpr, qrp,rpq, rqp
ইনপুট
str[] = "xyx", n = 2
আউটপুট
Result = "xyx"
ব্যাখ্যা
সাজানো ক্রমে সমস্ত সম্ভাব্য স্থানান্তর - xxy, xyx, yxx
পদ্ধতি
এখানে আমরা এই সমস্যা সমাধানের জন্য কিছু গাণিতিক ধারণা ব্যবহার করি।
ধারণাটি নিম্নলিখিত তথ্যের উপর ভিত্তি করে।
-
এখানে, N অক্ষর (সমস্ত স্বতন্ত্র) দ্বারা উত্পন্ন একটি স্ট্রিং-এর সর্বমোট পারমুটেশন সংখ্যা হল N!
-
এখন, N অক্ষর দ্বারা উত্পন্ন একটি স্ট্রিং-এর মোট ক্রমাগত সংখ্যা (এই ক্ষেত্রে C1 অক্ষরের ফ্রিকোয়েন্সি হল M1, C2 হল M2… এবং তাই Ck অক্ষরের ফ্রিকোয়েন্সি হল Mk) হল N!/(M1! * M2! *….এমকে!)।
-
আবার,
ঠিক করার পর N অক্ষর (সমস্ত স্বতন্ত্র) দ্বারা উত্পন্ন একটি স্ট্রিং-এর ক্রমাগত সংখ্যার মোট সংখ্যা
সমাধানে পৌঁছানোর জন্য নিচের ধাপগুলো অনুসরণ করা যেতে পারে।
-
প্রথমে, আমরা একটি অ্যারের ফ্রিকোয়েন্সিতে সমস্ত অক্ষরের ফ্রিকোয়েন্সি গণনা করি[]।
-
বর্তমানে স্ট্রিং-এ উপস্থিত প্রথম ক্ষুদ্রতম অক্ষর থেকে (ছোটতম সূচক i এরকম যে
-
ফ্রিকোয়েন্সি
-
দেখা গেছে যে এই যোগফলের মান দেওয়া n-এর চেয়ে বেশি হলে, তারপরে আমরা সেই অক্ষরটিকে প্রথম ফলাফলের আউটপুট অক্ষর, হ্রাস ফ্রিকোয়েন্সি [i] হিসাবে সেট করি এবং বাকি n-1 অক্ষরের জন্য একইভাবে চালিয়ে যাই।
-
এটি দেখা গেছে যে, অন্যদিকে, গণনাটি প্রয়োজনীয় n-এর চেয়ে ছোট হলে, ফ্রিকোয়েন্সি টেবিলের পরবর্তী অক্ষরের জন্য পুনরাবৃত্তি করুন এবং বারবার গণনাটি পরিবর্তন করুন যতক্ষণ না আমরা একটি অক্ষর নির্ধারণ করি যা একটি গণনা তৈরি করে প্রয়োজনীয় n.
এটি উল্লেখ করা উচিত যে উপরে উল্লিখিত পদ্ধতির সময় জটিলতা হল O(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
