C/C++で文字列の母音と子音を交互に並べ替えるアルゴリズム

母音と子音が混在した入力文字列が与えられたとき、母音と子音が交互に並ぶように文字列を並べ替える問題を考えます。このような交互配置が可能かどうかは、入力文字列が以下のいずれかの条件を満たしているかどうかで決まります。

• 母音と子音の数が同じであること。例えば、文字列「individual」は母音が5個、子音が5個です。

• 母音の方が多い場合は、母音と子音の数の差がちょうど1であること。例えば、文字列「noe」は母音が2個、子音が1個です。

• 子音の方が多い場合は、子音と母音の数の差がちょうど1であること。例えば、文字列「objective」は母音が4個、子音が5個です。

逆に言えば、母音と子音の数が2個以上異なる文字列は、交互に並べ替えることができません。

アルゴリズム

1. 母音の数を数える
2. 子音の数を数える
3. 母音と子音の数の差（どちらが多くても）が1より大きい場合はエラーを返す
4. 入力文字列を2つの部分に分割する：
    a) 1つ目の文字列には母音のみを含める
    b) 2つ目の文字列には子音のみを含める
5. 子音と母音の数が等しい場合、それぞれの文字列から交互に1文字ずつ取り出して最終的な文字列を作成する
6. 母音の方が多い場合：
    a) 余分な母音1文字を先頭に配置して、両文字列の長さを実質的に揃える
    b) それぞれの文字列から交互に1文字ずつ追加して最終的な文字列を作成する
7. 子音の方が多い場合：
    a) 余分な子音1文字を先頭に配置して、両文字列の長さを実質的に揃える
    b) それぞれの文字列から交互に1文字ずつ追加して最終的な文字列を作成する

実装例（C++）

以下に、上記のアルゴリズムをC++で実装したコードを示します。

#include <iostream>
#include <string>
using namespace std;
bool is_vowel(char ch) {
    if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch =='u') {
        return true;
    }
    return false;
}
string create_final_string(string &s1, string &s2, int start, int end) {
    string final_string;
    for (int i = 0, j = start; j < end; ++i, ++j) {
        final_string = (final_string + s1.at(i)) + s2.at(j);
    }
    return final_string;
}
string create_alternate_string(string &s) {
    int vowel_cnt, consonant_cnt;
    string vowel_str, consonant_str;
    vowel_cnt = consonant_cnt = 0;
    for (char c : s) {
        if (is_vowel(c)) {
            ++vowel_cnt;
            vowel_str += c;
        } else {
            ++consonant_cnt;
            consonant_str += c;
        }
    }
    if (abs(consonant_cnt - vowel_cnt) >= 2) {
        cerr << "String cannot be formed with alternating vowels and cosonants\n";
        exit(1);
    }
    if ((consonant_cnt - vowel_cnt) == 0) {
        return create_final_string(vowel_str, consonant_str, 0, vowel_cnt);
    } else if (vowel_cnt > consonant_cnt) {
        return vowel_str.at(0) + create_final_string(consonant_str, vowel_str, 1, vowel_cnt);
    }
    return consonant_str.at(0) + create_final_string(vowel_str, consonant_str, 1, consonant_cnt);
}
int main() {
    string s1 = "individual";
    string s2 = "noe";
    string s3 = "objective";
    cout << "Input : " << s1 << "\n";
    cout << "Output: " << create_alternate_string(s1) << "\n\n";
    cout << "Input : " << s2 << "\n";
    cout << "Output: " << create_alternate_string(s2) << "\n\n";
    cout << "Input : " << s3 << "\n";
    cout << "Output: " << create_alternate_string(s3) << "\n\n";
}

出力結果

上記のコードをコンパイルして実行すると、次のような出力が得られます。

Input : individual
Output: inidivudal

Input : noe
Output: one

Input : objective
Output: bojecitev

出力の解説

• individual（母音5・子音5）：数が等しいため、母音のみの文字列「iiiua」と子音のみの文字列「ndvdl」から交互に1文字ずつ取り出し、「inidivudal」が生成されます。

• noe（母音2・子音1）：母音が1個多いため、余分な母音「o」を先頭に置き、残りの母音と子音を交互に組み合わせて「one」が生成されます。

• objective（母音4・子音5）：子音が1個多いため、余分な子音「b」を先頭に置き、残りの文字を交互に組み合わせて「bojecitev」が生成されます。