C++で数値リストのすべての組み合わせを生成する方法（再帰アルゴリズム解説）

この記事では、与えられた数値リストから考えられるすべての組み合わせを生成するC++プログラムを紹介します。長さ1から配列の要素数まで、各長さごとの組み合わせを再帰的なアルゴリズムで効率よく列挙します。

アルゴリズムの概要

このプログラムは、各要素について「選ぶ／選ばない」という2つの選択肢を再帰的に評価することで、すべての組み合わせを網羅します。処理の流れは以下のとおりです。

Begin
    要素数と各要素を入力として受け取る。
    関数 Combi(char a[], int reqLen, int s, int currLen, bool check[], int l) :
    もし currLen > reqLen ならば
        処理を終了して戻る。
    そうでなければ currLen == reqLen のとき
        生成された新しい組み合わせを出力する。
    もし s == l ならば
        残りの要素がないため戻る。
    各インデックスには2つの選択肢がある：
        選択フラグを「true」として、currLen と s を増やしながら Combi() を再帰呼び出しする。
        または選択フラグを「false」として、s だけを増やして Combi() を再帰呼び出しする。
End

サンプルコード

以下は、指定された配列のすべての組み合わせを出力する完全な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;
    }
    check[s] = true;
    Combi(a, reqLen, s + 1, currLen + 1, check, l);
        // currLen と s を増やして Combi() を再帰的に呼び出す。
    check[s] = false;
    Combi(a, reqLen, s + 1, currLen, check, l);
        // s だけを増やして Combi() を再帰的に呼び出す。
}
int main() {
    int i,n;
    cout<<"Enter the number of element array have: ";
    cin>>n;
    bool check[n];
    char a[n];
    cout<<"\n";
    for(i = 0; i < n; i++) {
        cout<<"Enter "<<i+1<<" element: ";
        cin>>a[i];
        check[i] = false;
    }
    for(i = 1; i <= n; i++) {
        cout<<"\nThe all possible combination of length "<<i<<" for the given array set:\n";
        Combi(a, i, 0, 0, check, n);
    }
    return 0;
}

なお、元のコードでは bool check[n] の宣言が変数 n の入力前に記述されていましたが、これは未定義動作となる可能性があるため、上記のコードでは入力後に宣言するよう修正しています。

実行例

4つの要素 {4, 3, 2, 1} を入力した場合の実行結果は以下のとおりです。

Enter the number of element array have: 4
Enter 1 element: 4
Enter 2 element: 3
Enter 3 element: 2
Enter 4 element: 1
The all possible combination of length 1 for the given array set:
4
3
2
1
The all possible combination of length 2 for the given array set:
4 3
4 2
4 1
3 2
3 1
2 1
The all possible combination of length 3 for the given array set:
4 3 2
4 3 1
4 2 1
3 2 1
The all possible combination of length 4 for the given array set:
4 3 2 1

解説のポイント

• check[] 配列：各要素が現在の組み合わせに含まれているかどうかを記録するフラグ配列です。
• currLen：現在の組み合わせに含まれる要素数を追跡します。
• reqLen：目標とする組み合わせの長さです。currLen が reqLen に達した時点で組み合わせが出力されます。
• 計算量：組み合わせの総数は 2ⁿ 通り（部分集合の総数）になるため、要素数が大きくなると指数関数的に処理時間が増加します。

この手法はビットマスクを使った方法でも同様に実装できますが、再帰によるバックトラッキングはロジックが直感的で理解しやすいのが特徴です。