精進記録

言語はc++です

Ｎ個からＫ個取り出す組み合わせの列挙

競プロ

簡単のため、まずＮ（＞３）個の整数｛１，２，３，，，Ｎ－１，Ｎ｝のうちから３個取り出す組み合わせの列挙を考えます。

#include<bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define each(it,v) for(auto &it : v)
#define mod 1000000007
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define vl vector<long>
#define P pair<int,int>
using namespace std;

main()
{
        int n; cin>>n;

        vector<vi> u;
        for(int i=0;i<n-2;i++)
        {
                for(int j=i+1;j<n-1;j++)
                {
                        for(int k=j+1;k<n;k++)
                        {
                                vi v={i+1,j+1,k+1};
                                u.push_back(v);
                        }
                }
        }

        each(v,u)
        {
                each(it,v)cout<<it<<" ";
                cout<<endl;
        }
}
//マクロをふんだんに使っており読みづらいかと思います。ごめんなさい。

これによりｎ＝５を入力としたときは、

5
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

が出力できます。

取り出す個数が固定されており、かつ、３個のみと少ない個数であるためfor文を回すだけで実現しました。
lucky pin問題でこんなようなコードを書いた記憶があります。

これが３個ではなくＫ個となってくるとfor文では太刀打ちできませんので工夫します。

そこで

ループ回数も動的に対応できるよう再帰関数にしました。

int n;

void f(int k,vi v)
{
        if(k==0)
        {
                each(it,v)cout<<it<<" ";
                cout<<endl;
        }else
        {
                rep(i,n)
                {
                        vi u=v;
                        u.push_back(i+1);
                        f(k-1,u);
                }
        }
}


main()
{
        int k; cin>>n>>k;
        vi v;
        f(k,v);
}

参考コード：こちらの１６ページ
たとえばｎ＝７，ｋ＝３と入力させた場合、

7 3
1 1 1 
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 2 1
1 2 2
1 2 3
1 2 4
1 2 5
1 2 6
1 2 7
1 3 1
1 3 2
1 3 3
1 3 4
1 3 5
1 3 6
1 3 7
1 4 1
1 4 2 
1 4 3
1 4 4
1 4 5 
1 4 6
1 4 7
1 5 1
1 5 2
1 5 3
1 5 4
1 5 5
1 5 6
1 5 7 
1 6 1
1 6 2
1 6 3
1 6 4
1 6 5
1 6 6
1 6 7
1 7 1
1 7 2
1 7 3
1 7 4
1 7 5
1 7 6
1 7 7
2 1 1 
2 1 2
2 1 3
・
・
・
・
・
・
・
・
・
・
7 3 6
7 3 7
7 4 1
7 4 2
7 4 3
7 4 4
7 4 5
7 4 6
7 4 7
7 5 1
7 5 2
7 5 3
7 5 4
7 5 5
7 5 6
7 5 7
7 6 1
7 6 2
7 6 3
7 6 4
7 6 5
7 6 6
7 6 7
7 7 1 
7 7 2
7 7 3
7 7 4
7 7 5
7 7 6
7 7 7

となります。
これは組み合わせの列挙ではないですね。
しかも計算量がＯ（nk）と非現実的すぎます。

setを使おう

int n;

void f(int k,set<int> s)
{
        if(k==0)
        {
                each(it,s)cout<<it<<" ";
                cout<<endl;
        }else
        {
                rep(i,n)
                {
                        set<int> t=s;
                        if(!t.count(i+1))
                        {
                                t.insert(i+1);
                                f(k-1,t);
                        }
                }
        }
}


main()
{
        int k; cin>>n>>k;
        set<int> s;
        f(k,s);
}

setの中身を１度確認してから要素を入れるか入れないかを判断させています。
中にすでに同じものがあるかどうかの判断にs.count(x)が使えそうだなと思ったので使ってみています。
ｎ＝４，ｋ＝３と入力させた場合、

4 3
1 2 3 
1 2 4
1 2 3
1 3 4
1 2 4
1 3 4
1 2 3
1 2 4
1 2 3
2 3 4
1 2 4 
2 3 4
1 2 3
1 3 4
1 2 3
2 3 4
1 3 4
2 3 4
1 2 4
1 3 4
1 2 4 
2 3 4
1 3 4
2 3 4

同じものが重複して出力されています。
まとめて１つのset<set>に入れてやれば目的を達成できないこともないかもしれません。

int n;
set<set<int>> comb;

void f(int k,set<int> s)
{
        if(k==0)
        {
                comb.insert(s);
        }else
        {
                rep(i,n)
                {
                        set<int> t=s;
                        if(!t.count(i+1))
                        {
                                t.insert(i+1);
                                f(k-1,t);
                        }
                }
        }
}

main()
{
        int k; cin>>n>>k;
        set<int> s;
        f(k,s);
        each(s,comb)
        {
                each(it,s)cout<<it<<" ";
                cout<<endl;
        }
}

１つの大きなsetにまとめました。
ｎ＝４，ｋ＝３の出力は以下のようになります。

4 3
1 2 3 
1 2 4 
1 3 4
2 3 4

１つの大きなsetにまとめるのは少し面倒なので

int n;

void f(int k,set<int> s)
{
        if(k==0)
        {
                each(it,s)cout<<it<<" ";
                cout<<endl;
        }else
        {
                rep(i,n)
                {
                        set<int> t=s;
                        if(t.empty())
                        {
                                t.insert(i+1);
                                f(k-1,t);
                        }else if(*rbegin(t)<i+1)
                        {
                                t.insert(i+1);
                                f(k-1,t);
                        }
                }
        }
}


main()
{
        int k; cin>>n>>k;
        set<int> s;
        f(k,s);
}

setの中の最大値*rbegin(t)を使う事によって大きなsetの中にまとめる作業を省くことに成功しました。
具体的には「setの中にある要素たちより大きい数字しか入れない」をしています。
これによって、例えば

1 2 3 4 5 6 7 8

と並んでいるうち、1と4を既に要素として持っている場合、
「最大値より大きい数字しか見ない」とは「4より右側のみを見る」ことになります。
探索の方向が右方向に固定できるので「あっちから数字持ってきたりこっちから持ってきたり最終的に同じ組み合わせが出来ちゃった（重複）」が発生しません。
このようにif文をもってして重複パターンを回避できているので、このコードに関してはsetではなくvectorのほうが（計算量的に）よいかもしれません。（中身は必ずsortされているので）（setのinsertは対数時間かかる）

結論

#include<bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define each(it,v) for(auto &it : v)
#define mod 1000000007
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define vl vector<long>
#define P pair<int,int>
using namespace std;

int n;

void f(int k,vi v)
{
        if(k==0)
        {
                each(it,v)cout<<it<<" ";
                cout<<endl;
        }else
        {
                rep(i,n)
                {
                        vi u=v;
                        if(u.size()==0)
                        {
                                u.push_back(i+1);
                                f(k-1,u);
                        }else if(u.back()<i+1)
                        {
                                u.push_back(i+1);
                                f(k-1,u);
                        }
                }
        }
}


main()
{
        int k; cin>>n>>k;
        vi v;
        f(k,v);
}

とりあえず現状はこんなようなものかなと思います。
ここまでお読み頂きありがとうございました！