与えられた文字列の順列の数を見つけるためのC++プログラム

文字列の文字をさまざまな順序で並べることができます。ここでは、特定の文字列から形成できる順列の数をカウントする方法を説明します。

1つの文字列が「abc」の場合はわかります。 3つの文字があります。 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