母音と子音の相対的な位置を変えずに単語を並べ替える方法とは？

n個の要素（n < 10）からなる文字列が与えられたとします。ここで求めたいのは、母音と子音それぞれの相対的な位置関係を崩さずに、この文字列を並べ替える方法が何通りあるかという問題です。

解き方は非常にシンプルです。まず、与えられた文字列に含まれる母音と子音の個数をそれぞれ数えます。次に、母音だけを並べ替えた場合の組み合わせ数を求め、同じように子音だけを並べ替えた場合の組み合わせ数を求めます。最後に、この2つの値を掛け合わせることで、並べ方の総数が得られます。

アルゴリズム

arrangeWayCount(str)

Begin
    頻度を格納するための配列「freq」を定義する
    各文字の出現頻度を数えてfreq配列に記録する。
    たとえばfreq[0]には「a」の頻度、freq[1]には「b」の頻度を格納していく。
    v := str内の母音の数、c := str内の子音の数
    vArrange := v の階乗
    [a, e, i, o, u] の各母音 v について、次を繰り返す
        vArrange := vArrange ÷ （v の出現頻度の階乗）
    繰り返し終了
    cArrange := c の階乗
    各子音 con について、次を繰り返す
        cArrange := cArrange ÷ （con の出現頻度の階乗）
    繰り返し終了
    return vArrange × cArrange
End

実装例

#include <iostream>
using namespace std;
long long factorial(int n){
    if(n == 0 || n == 1)
        return 1;
    return n*factorial(n-1);
}
long long arrangeWayCount(string str){
    long long freq[27] = {0}; // 頻度配列を0で初期化
    int v = 0, c = 0;
    for (int i = 0; i < str.length(); i++) {
        freq[str[i] - 'a']++;
        if (str[i] == 'a' || str[i] == 'e' || str[i] == 'i' || str[i] == 'o' || str[i] == 'u') {
            v++;
        }else
            c++;
    }
    long long arrangeVowel;
    arrangeVowel = factorial(v);
    arrangeVowel /= factorial(freq[0]); // 母音 a
    arrangeVowel /= factorial(freq[4]); // 母音 e
    arrangeVowel /= factorial(freq[8]); // 母音 i
    arrangeVowel /= factorial(freq[14]); // 母音 o
    arrangeVowel /= factorial(freq[20]); // 母音 u
    long long arrangeConsonant;
    arrangeConsonant = factorial(c);
    for (int i = 0; i < 26; i++) {
        if (i != 0 && i != 4 && i != 8 && i != 14 && i != 20)
        arrangeConsonant /= factorial(freq[i]); // 母音以外のすべての文字の頻度
    }
    long long total = arrangeVowel * arrangeConsonant;
    return total;
}
main() {
    string str = "computer";
    long long ans = arrangeWayCount(str);
    cout << "Possible ways to arrange: " << ans << endl;
}

実行結果

Possible ways to arrange: 720

この結果の理由を確認してみましょう。例として使った「computer」という文字列には、母音が o・u・e の3つ、子音が c・m・p・t・r の5つ含まれています。母音はすべて異なるため並べ方は 3! = 6 通り、子音も重複がないため 5! = 120 通りとなります。したがって、全体の並べ方は 6 × 120 = 720 通りとなり、プログラムの出力と一致します。