C++で文字列の順列の総数を求めるプログラムの作成方法

文字列に含まれる文字は、さまざまな順序で並べ替えることができます。本記事では、与えられた文字列から作成できる順列の数を求める方法を解説します。

たとえば「abc」という3文字の文字列の場合、並べ方は 3! = 6 通りあります。つまり、n 文字の文字列であれば、最大で n! 通りの並べ方が存在します。しかし、「aab」のように同じ文字が複数回含まれている場合、単純に 6 通りにはなりません。

「aab」の全パターンを書き出してみると、次のようになります。

• aba
• aab
• baa
• baa
• aab
• aba

このうち、(1番目と6番目)、(2番目と5番目)、(3番目と4番目) のペアはそれぞれ同一の並び方です。したがって、実際の順列の数は 3 となります。

これを一般化すると、順列の総数は次の式で表せます。

順列の総数 = n! ÷ (2回以上出現する各文字の出現回数の階乗の積)

この問題を解く手順は以下のとおりです。

アルゴリズムの手順

1. まず、文字列に含まれるすべての文字の出現頻度を計算します。
2. 次に、文字列の長さ n の階乗(n!)を求めます。
3. 最後に、出現回数が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']++; // 各文字の出現頻度を個別にカウント
    }
    int res = fact(str.size()); // 長さnの文字列に対してn!を計算
    for(int i = 0; i<26; i++) {
        if(freq[i] > 1)
            res /= fact(freq[i]); // n!を(各文字の出現回数)!で割る
    }
    return res;
}
main(){
    string n;
    cout << "Enter a string to count number of permutations can be possible: ";
    cin >> n;
    cout << "\nThe number of permutations: " << countPermutation(n);
}

実行結果

Enter a string to count number of permutations can be possible: abbc
The number of permutations: 12

解説

入力例の「abbc」は4文字なので、重複を考慮しない場合の並べ方は 4! = 24 通りです。しかし、文字「b」が2回含まれているため、2!(= 2)で割る必要があります。よって 24 ÷ 2 = 12 となり、順列の総数は 12 通りであることが確認できます。

なお、このプログラムでは小文字の英字(a〜z)のみを想定しています。大文字や記号なども扱いたい場合は、頻度配列のサイズを拡張するか、mapコンテナを使用して文字ごとの出現回数を管理するとよいでしょう。また、文字列が長くなると階乗の値が急激に大きくなるため、オーバーフロー対策として long long 型や多倍長整数の利用も検討してください。