C ++程序查找给定字符串的排列数
我们可以按不同顺序排列字符串的字符。在这里，我们将看到如何计算给定字符串可以形成的排列数量。
我们知道如果一个字符串是'abc'。它具有三个字符；我们可以将它们分成3个！=6种不同的方式。因此，一个包含n个字符的字符串，我们可以将它们排列成n个！不同的方法。但是现在，如果多次出现相同的字符（例如aab），那么将不会有6个排列。
aba
阿卜
a
a
阿卜
aba
这里(1,6)，（2、5），(3,4)相同。因此，这里的排列数为3。这基本上是（n！）/（出现多次的所有字符的阶乘之和）。
为了解决这个问题，首先我们必须计算所有字符的频率。然后计算n的阶乘，然后将所有大于1的频率值之和除以n。
范例程式码
#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