একটি স্ট্রিং (লোয়ারকেস) ও পূর্ণসংখ্যা n দেওয়া আছে। স্ট্রিংটির সব পারমিউটেশন লেক্সিকোগ্রাফিক্যালি সর্ট করা হলে n-তম পারমিউটেশন কী তা বের করতে হবে। ফ্যাক্টোরিয়াল ও ফ্রিকোয়েন্সি কাউন্ট ব্যবহার করে O(দৈর্ঘ্য) তে সমাধান।
উদাহরণ
str = "pqr", n = 3 → "qpr" str = "xyx", n = 2 → "xyx"
অ্যালগরিদম
- ফ্যাক্টোরিয়াল প্রিকম্পিউট করুন।
- প্রতিটি ক্যারেক্টারের ফ্রিকোয়েন্সি কাউন্ট করুন।
- স্মলেস্ট ক্যারেক্টার থেকে শুরু করে: সেটি ফিক্স করলে কতটি পারমিউটেশন সম্ভব তা বের করুন।
- যদি সেটি ≥ n হয়, সেটি বেছে নিন এবং n আপডেট করুন। নাহলে পরবর্তী ক্যারেক্টার চেক করুন।
C++ প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAX_CHAR = 26, MAX_FACT = 20;
ll fact[MAX_FACT];
void precompute() {
fact[0] = 1;
for (int i=1;i= n) {
out[k++] = i+'a';
n -= (sum - xsum);
break;
}
if (sum < n) freq[i]++;
}
}
for (int i=MAX_CHAR-1; k=0; i--)
if (freq[i]) { out[k++] = i+'a'; freq[i]--; }
out[k] = '\0';
cout << out;
}
int main() {
char str[] = "tutorialspoint";
int n = 5;
nPermute(str, n);
return 0;
}
আউটপুট: aiilnooprtsttu
