আমরা একটি স্ট্রিং এর অক্ষরকে বিভিন্ন ক্রমে সাজাতে পারি। এখানে আমরা দেখব কিভাবে আমরা একটি প্রদত্ত স্ট্রিং থেকে গঠনের সংখ্যা গণনা করতে পারি।
আমরা জানি যে একটি স্ট্রিং যদি 'abc' হয়। এতে তিনটি অক্ষর আছে; আমরা তাদের 3 তে সাজাতে পারি! =6টি ভিন্ন উপায়। তাই n অক্ষর সহ একটি স্ট্রিং, আমরা তাদের n এ সাজাতে পারি! ভিন্ন পথ. কিন্তু এখন যদি একই অক্ষর একাধিকবার উপস্থিত থাকে, যেমন aab, তাহলে 6টি স্থানান্তর হবে না।
- aba
- aab
- baa
- baa
- aab
- aba
এখানে (1,6), (2, 5), (3,4) একই। তাই এখানে পারমুটেশনের সংখ্যা 3। এটি মূলত (n!)/(সমস্ত অক্ষরের ফ্যাক্টরিয়ালের যোগফল যা একাধিকবার ঘটছে)।
এই সমস্যাটি সমাধান করার জন্য, প্রথমে আমাদের সমস্ত অক্ষরের ফ্রিকোয়েন্সি গণনা করতে হবে। তারপর n-এর ফ্যাক্টরিয়াল গণনা করুন, তারপর 1-এর থেকে বড় সমস্ত ফ্রিকোয়েন্সি মানের যোগফল দিয়ে ভাগ করুন।
উদাহরণ কোড
#include<iostream>
using namespace std;
long fact(long n) {
if(n == 0 || n == 1 )
return 1;
return n*fact(n-1);
}
int countPermutation(string str) {
int freq[26] = {0};
for(int i = 0; i<str.size(); i++) {
freq[str[i] - 'a']++; //get the frequency of each characters individually
}
int res = fact(str.size()); //n! for string of length n
for(int i = 0; i<26; i++) {
if(freq[i] > 1)
res /= fact(freq[i]); //divide n! by (number of occurrences of each characters)!
}
return res;
}
main(){
string n;
cout << "Enter a number to count number of permutations can be possible: ";
cin >> n;
cout << "\nThe number of permutations: " << countPermutation(n);
} আউটপুট
Enter a number to count number of permutations can be possible: abbc The number of permutations: 12
