C++でサイズnの配列からr個の要素を選ぶすべての組み合わせを出力する方法

この記事では、サイズnの配列と正の整数rが与えられたとき、配列の要素から選んだサイズrのすべての組み合わせを出力する方法を解説します。

具体例を見て、問題のイメージをつかみましょう。

入力: {5, 6, 7, 8} ; r = 3
出力: {5, 6, 7}, {5, 6, 8}, {5, 7, 8}, {6, 7, 8}

解法1：要素を固定して再帰的に探索する

この問題に対する基本的なアプローチは、一部の要素を固定し、残りの要素に対して再帰（またはループ）を回してすべての組み合わせを見つけるというものです。ポイントは、先頭の n-r+1 個の要素だけを固定対象にすればよいという点です。それ以降の要素を先頭に固定すると、残りの要素数が足りず、サイズrの組み合わせが作れないためです。

コード例

#include<iostream>
using namespace std;

// サイズrの組み合わせを再帰的に生成して出力する関数
void printRElementCombination(int arr[], int combination[], int start, int end, int index, int r){
    // r個の要素が確定したら組み合わせを出力
    if (index == r){
        cout << "{ ";
        for (int j = 0; j < r; j++)
            cout << combination[j] << " ";
        cout << "}\t";
        return;
    }
    // 残りの要素数が組み合わせに必要な数を満たす範囲でループ
    for (int i = start; i <= end && end - i + 1 >= r - index; i++){
        combination[index] = arr[i];
        printRElementCombination(arr, combination, i+1, end, index+1, r);
    }
}

int main(){
    int arr[] = {1, 2, 3, 4, 5};
    int r = 3;   // 選ぶ要素数
    int n = 5;   // 配列のサイズ
    int combination[r];

    cout << "The combination is : \n";
    printRElementCombination(arr, combination, 0, n-1, 0, r);
    return 0;
}

出力結果

The combination is −
{ 1 2 3 } { 1 2 4 } { 1 2 5 } { 1 3 4 } { 1 3 5 } { 1 4 5 }
{ 2 3 4 } { 2 3 5 } { 2 4 5 } { 3 4 5 }

解法2：要素を「含める／含めない」で判定する

同じ問題は、現在の要素を組み合わせに含めるかどうかを判定しながら再帰的に処理する方法でも解けます。考え方は解法1と同じで、再帰を通じて要素を順に処理し、組み合わせをcombo配列に格納していきます。ただし、この方法では要素を明示的に固定せず、各要素について「含める場合」と「含めない場合」の2つの分岐を再帰的に探索します。

コード例

#include <iostream>
using namespace std;

// 各要素を含める/含めないの2択で再帰的に組み合わせを生成する関数
void combinationUtil(int arr[], int n, int r, int index, int combo[], int i){
    // r個の要素が確定したら組み合わせを出力
    if (index == r){
        cout << "{";
        for (int j = 0; j < r; j++)
            cout << combo[j] << " ";
        cout << "}\t";
        return;
    }
    // 配列の末尾まで到達したら終了
    if (i >= n)
        return;

    // 現在の要素 arr[i] を組み合わせに含める場合
    combo[index] = arr[i];
    combinationUtil(arr, n, r, index + 1, combo, i + 1);

    // 現在の要素 arr[i] を組み合わせに含めない場合
    combinationUtil(arr, n, r, index, combo, i + 1);
}

int main(){
    int arr[] = {1, 2, 3, 4, 5};
    int r = 3;   // 選ぶ要素数
    int n = 5;   // 配列のサイズ
    int combo[r];

    cout << "The combination is : \n";
    combinationUtil(arr, n, r, 0, combo, 0);
    return 0;
}

出力結果

The combination is −
{1 2 3 } {1 2 4 } {1 2 5 } {1 3 4 } {1 3 5 } {1 4 5 }
{2 3 4 } {2 3 5 } {2 4 5 } {3 4 5 }

まとめ

どちらの方法でも、サイズnの配列からr個の要素を選ぶすべての組み合わせを正しく出力できます。解法1は「開始位置をずらしながら固定する」シンプルな構造で理解しやすく、解法2は「各要素を含めるかどうかの二分決定」で組み合わせを列挙するため、部分集合を扱う他の問題にも応用しやすいのが特徴です。計算量はいずれも組み合わせの総数 O(nCr) に比例します。