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