हम एक स्ट्रिंग के पात्रों को अलग-अलग क्रम में व्यवस्थित कर सकते हैं। यहां हम देखेंगे कि हम कैसे गिन सकते हैं कि किसी दिए गए स्ट्रिंग से कितने क्रमपरिवर्तन बन सकते हैं।
हम जानते हैं कि यदि एक स्ट्रिंग 'abc' है। इसमें तीन वर्ण हैं; हम उन्हें 3 में व्यवस्थित कर सकते हैं! =6 अलग-अलग तरीके। तो n वर्णों वाली एक स्ट्रिंग, हम उन्हें n में व्यवस्थित कर सकते हैं! विभिन्न तरीके। लेकिन अब अगर एक ही वर्ण कई बार मौजूद हैं, जैसे आब, तो 6 क्रमपरिवर्तन नहीं होंगे।
- अबा
- आब
- बा
- बा
- आब
- अबा
यहाँ (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