[c++] n個からr個の組合せ列挙

n個からr個の組合せ列挙するライブラリを作成しました。
列挙した組合せを2次元配列(vector)に格納して、返すようにしています。
おそらく、あまり性能は良くないです。。。

再帰的に走査して組合せ作成する関数dfs_combinationを作成しましたが、引数が多くなってしまったので、最初の呼び出し用に関数combinationを用意しました。

combination("元になる配列arr", "取り出す要素数r")
といった感じにして、引数2つで呼べるようにしてます。

内容

関数dfs_combination
結果を変数resultに格納するようにしています

配列arr：　元になる配列
変数idx:　配列arrのindex。現在みている要素を表す。
変数 r：　列挙する数
配列pattern：　今作成中の組合せのパターン1つ
2次元配列 result：　生成した全ての組合せパターン

template <class T>
void dfs_combination(vector<T> &arr, int idx, int r, vector<T> &pattern, vector<vector<T>> &result) {
    if (r == 0) {
        result.push_back(pattern);
        return;
    }
    if ((idx + r) > arr.size()) {
        return;
    }

    // select
    pattern.push_back(arr[idx]);
    dfs_combination(arr, idx + 1, r - 1, pattern, result);
    pattern.pop_back();
    // not select
    dfs_combination(arr, idx + 1, r, pattern, result);
}

関数combination
関数dfs_combinationを呼び出すための関数です。

配列arr：　元になる配列
変数 r：　列挙する数

template <class T>
vector<vector<T>> combination(vector<T> &arr, int r) {
    if (arr.size() < r) {
        printf("combination ERROR: r is larger than arr.size()\n");
        exit(1);
    }

    vector<T> pattern;
    vector<vector<T>> result;
    dfs_combination(arr, 0, r, pattern, result);
    return result;
}

code

動作例になります。
以下の2つの例になります
・配列[0, 1, 2, 3, 4]から3個取り出す組合せ
・配列["aa", "aa", "cc", "dd", "ee"]から3個取り出す組合せ

デバッグ用に、2次元配列の内容を表示する関数を用意していますが、こちらの説明は割愛します。

#include <iostream>
#include <vector>
using namespace std;
#include <numeric>


// Combination  nCr ----------
template <class T>
void dfs_combination(vector<T> &arr, int idx, int r, vector<T> &pattern, vector<vector<T>> &result) {
    if (r == 0) {
        result.push_back(pattern);
        return;
    }
    if ((idx + r) > arr.size()) {
        return;
    }

    // select
    pattern.push_back(arr[idx]);
    dfs_combination(arr, idx + 1, r - 1, pattern, result);
    pattern.pop_back();
    // not select
    dfs_combination(arr, idx + 1, r, pattern, result);
}

template <class T>
vector<vector<T>> combination(vector<T> &arr, int r) {
    if (arr.size() < r) {
        printf("combination ERROR: r is larger than arr.size()\n");
        exit(1);
    }

    vector<T> pattern;
    vector<vector<T>> result;
    dfs_combination(arr, 0, r, pattern, result);
    return result;
}
// ------------------------------

// Debug用  配列の表示 ----------
template <class T>
void print_vector(vector<T> arr) {
    printf("[ ");
    for (int i = 0; i < arr.size(); i++) {
        //printf("%d", arr[i]);
        cout << arr[i];
        if (i != (arr.size() - 1)) printf(", ");
    }
    printf(" ]\n");
}

template <class T>
void print_vector2(vector<T> arr) {
    for (int i = 0; i < arr.size(); i++) {
        print_vector(arr[i]);
    }
}
// ------------------------------


int main() {
    vector<int> arr(5);
    iota(arr.begin(), arr.end(), 0);
    vector<vector<int>> res = combination(arr, 3);
    print_vector2(res);

    vector<string> arr2 = {"aa", "aa", "cc", "dd", "ee"};
    vector<vector<string>> res2 = combination(arr2, 3);
    print_vector2(res2);
}

実行結果は、以下のような感じ。

[ 0, 1, 2 ]
[ 0, 1, 3 ]
[ 0, 1, 4 ]
[ 0, 2, 3 ]
[ 0, 2, 4 ]
[ 0, 3, 4 ]
[ 1, 2, 3 ]
[ 1, 2, 4 ]
[ 1, 3, 4 ]
[ 2, 3, 4 ]
[ aa, aa, cc ]
[ aa, aa, dd ]
[ aa, aa, ee ]
[ aa, cc, dd ]
[ aa, cc, ee ]
[ aa, dd, ee ]
[ aa, cc, dd ]
[ aa, cc, ee ]
[ aa, dd, ee ]
[ cc, dd, ee ]