被りあり・なし組み合わせ列挙 (c++)

自分の記録用に書きます。

ググった時に
pythonのitertools.combination的なものが見つからなかったのでここに書きます。

中でdfsやっています。
vectorで返すようにしています。

被りなしの組み合わせ

comb.cpp

#include <bits/stdc++.h>
#include <cstdint>
using namespace std;

template<typename T>
vector<vector<T>> combination(vector<T> &elems, int r) {
    vector<vector<T>> v{};
    vector<T> v1(r);
    int n = elems.size();
    function<void(int,int,int)> _dfs = [&](int bit,int now,int num_decided){
        if (num_decided == r) {
            int index = 0;
            for(int i=0; i<n;i++){
                if(bit&(1<<i)){
                    v1[index] = elems[i];
                    index++;
                }
            }
            v.push_back(v1);
            return;
        }
        if(now == n)return;
        _dfs(bit+(1<<now),now+1,num_decided+1);
        _dfs(bit,now+1,num_decided);
    };
    _dfs(0,0,0);
    return v;
}

int main()
{
    int N=5,R=2;
    vector<char> elems(N);

    for (int i = 0; i < N; i++) {
        elems[i] = 'A' + i;
    }
    vector<vector<char>> c = combination(elems, R);
    for(auto i: c){
        for(char j: i){
            cout << j <<" ";
        }
        cout << endl;
    }
	return 0;
}

A B 
A C 
A D 
A E 
B C 
B D 
B E 
C D 
C E 
D E

被りありの組み合わせ

combination.cpp

template<typename T>
vector<vector<T>> combination(vector<T> &elems, int r) {
    vector<vector<T>> v{};
    vector<T> v1(r);
    map<T,int> m{};
    for(T &i: elems)m[i]++;
    vector<T> elem{};
    for(auto iter = m.begin(); iter != m.end(); iter++)elem.push_back(iter->first);

    int n = elems.size();
    function<void(int,int)> _dfs = [&](int now,int num_decided){
        if(num_decided > r)
            return;
        if (num_decided == r) {
            v.push_back(v1);
            return;
        }
        if(now == elem.size())
            return;
        for(int i=0;i<=m[elem[now]];i++){
            // i==0の時は追加しないとき
            if(i==0){
                _dfs(now+1,num_decided);
            }else{
                v1[num_decided+(i-1)] = elem[now];
                _dfs(now+1,num_decided+i);
            }
        }
    };
    _dfs(0,0);
    return v;
}

int main()
{
    int N=6,R=3;
    vector<int> elems{0,1,1,1,2,3};
    vector<vector<int>> c = combination(elems, R);
    for(auto i: c){
        for(int j: i){
            cout << j <<" ";
        }
        cout << endl;
    }
	return 0;
}

1 2 3 
1 1 3 
1 1 2 
1 1 1 
0 2 3 
0 1 3 
0 1 2 
0 1 1 

ちなみに、かぶりありの時をchatgptに書かせてみた

#include <bits/stdc++.h>
#include <cstdint>
using namespace std;

// 組み合わせ列挙アルゴリズムの実装
void combination(vector<int>& nums, int k, vector<vector<int>>& result, vector<int>& path, int start) {
    if (path.size() == k) {
        result.push_back(path);
        return;
    }
    for (int i = start; i < nums.size(); i++) {
        if (i > start && nums[i] == nums[i-1]) continue; // 同じ数をスキップ
        path.push_back(nums[i]);
        combination(nums, k, result, path, i + 1); // 次の要素から開始
        path.pop_back();
    }
}

int main() {
    vector<int> nums = { 2, 2, 2,2,2,2};
    int k = 3;
    vector<vector<int>> result;
    vector<int> path;
    sort(nums.begin(), nums.end()); // numsを昇順にソート
    combination(nums, k, result, path, 0);
    for (auto v : result) {
        for (auto i : v) {
            cout << i << " ";
        }
        cout << endl;
    }
    return 0;
}

動いていそう...すごすぎ

もし、間違っていることがあったり、もっと早くできる等あればご連絡ください。

参考