a、b、c、d、eからすべての可能な組み合わせを生成するC++プログラム

この記事では、a、b、c、d、eの5つの文字から考えられるすべての組み合わせを生成するC++プログラムを紹介します。再帰呼び出しを利用したシンプルな手法で、長さ1から5までの全パターン（合計31通り）を出力します。

アルゴリズム

組み合わせの生成は、各要素について「選ぶ／選ばない」の2択を順番に決めていくことで実現できます。全体の流れを擬似コードで表すと次のようになります。

開始
    要素数と各要素を入力として受け取る。
    関数 Combi(char a[], int reqLen, int s, int currLen, bool check[], int l)
    （与えられた配列のすべての組み合わせを出力する）
    //
    各引数の意味：
    char a[]   = 文字配列
    reqLen     = 必要な長さ（生成する組み合わせの長さ）
    s          = 処理中の開始位置
    currLen    = 現在の組み合わせの長さ
    check[]    = 各要素を選択したかどうかを示すブール値の配列
    l          = 配列の長さ
    //
    関数の処理内容：
        もし currLen > reqLen なら
            return（処理を終了）
        そうでなければ currLen == reqLen のとき
            新しく生成された組み合わせを出力する。
        もし s == l なら
            それ以上要素が残っていないので return する。
        各インデックスには2つの選択肢がある：
        ・check[s] を true にして、currLen と s を1ずつ増やして Combi() を再帰呼び出しする。
        ・check[s] を false にして、s だけを1増やして Combi() を再帰呼び出しする。
終了

C++による実装例

#include<iostream>
using namespace std;

// すべての組み合わせを生成して出力する関数
void Combi(char a[], int reqLen, int s, int currLen, bool check[], int l)
{
    // 現在の長さが必要な長さを超えたら終了
    if(currLen > reqLen)
        return;
    // 必要な長さに達したら、選択済みの文字を出力
    else if (currLen == reqLen) {
        cout<<"\t";
        for (int i = 0; i < l; i++) {
            if (check[i] == true) {
                cout<<a[i]<<" ";
            }
        }
        cout<<"\n";
        return;
    }
    // それ以上要素が残っていなければ終了
    if (s == l) {
        return;
    }
    // パターン1：現在の要素を選択する場合
    check[s] = true;
    Combi(a, reqLen, s + 1, currLen + 1, check, l);
    // パターン2：現在の要素を選択しない場合
    check[s] = false;
    Combi(a, reqLen, s + 1, currLen, check, l);
}

int main() {
    int i,n;
    cout<<"配列の要素数を入力してください: ";
    cin>>n;
    bool check[n];
    char a[n];
    cout<<"\n";
    for(i = 0; i < n; i++) {
        cout<<i+1<<"番目の要素を入力してください: ";
        cin>>a[i];
        check[i] = false;
    }
    for(i = 1; i <= n; i++) {
        cout<<"\n長さ "<<i<<" のすべての組み合わせ:\n";
        Combi(a, i, 0, 0, check, n);
    }
    return 0;
}

実行結果

配列の要素数を入力してください: 5
1番目の要素を入力してください: a
2番目の要素を入力してください: b
3番目の要素を入力してください: c
4番目の要素を入力してください: d
5番目の要素を入力してください: e

長さ 1 のすべての組み合わせ:
a
b
c
d
e

長さ 2 のすべての組み合わせ:
a b
a c
a d
a e
b c
b d
b e
c d
c e
d e

長さ 3 のすべての組み合わせ:
a b c
a b d
a b e
a c d
a c e
a d e
b c d
b c e
b d e
c d e

長さ 4 のすべての組み合わせ:
a b c d
a b c e
a b d e
a c d e
b c d e

長さ 5 のすべての組み合わせ:
a b c d e

プログラムのポイント

このプログラムの動作を理解するうえで、押さえておきたいポイントをまとめます。

1. 再帰による「選ぶ／選ばない」の分岐

関数Combi()は、インデックスsの要素に対して必ず2回自分自身を呼び出します。1回目はその要素をtrue（選択）として次へ進み、2回目はfalse（未選択）として進みます。この分岐をすべての要素に対して繰り返すことで、あらゆる選択パターンが漏れなく網羅されます。

2. 組み合わせの総数は二項係数と一致

n個の要素からk個を選ぶ組み合わせの数は「nCk」で表されます。5文字の場合、長さ1〜5それぞれについて 5、10、10、5、1 通りとなり、合計は 2⁵ − 1 = 31 通りです。実行結果の出力行数もこの数と一致していることが確認できます。

3. 可変長配列に関する注意

サンプルコードで使っているchar a[n]やbool check[n]のような可変長配列（VLA）は、厳密には標準C++の機能ではなく、GCCなど一部コンパイラの拡張機能です。移植性を重視する場合は、std::vector<char>やstd::vector<bool>を使用することをおすすめします。