読者です 読者をやめる 読者になる 読者になる

C++で、重複順列を全列挙する

programming contest C++

このエントリーをはてなブックマークに追加

異なるn個のものから、重複を許してr個を取り出して列をつくることを、n個からr個とる重複順列という。これをC++で全列挙することを考える。

例題として、1〜5の数字を使ってできる3桁の数字を全列挙することを考える。そのコードは以下の通り。

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

vector<int> buf;

void dfs(int i, const int size, const int range_start, const int range_end)
{
    if (i == size) {
        // ここで所望の作業を行う
        for(int i = 0; i < buf.size(); ++i){
            cout << buf[i] << " ";
        }
        cout << endl;
    }
    else{
        for(int j = range_start; j <= range_end; ++j){
            buf[i] = j;
            dfs(i + 1, size, range_start, range_end);
        }
    }
}

int main(void)
{
    int size = 3;
    int range_start = 1;
    int range_end = 5;
    
    buf.resize(size);
    dfs(0, size, range_start, range_end);

    return 0;
}

出力は以下の通り。5の3乗で125個の数が生成される。

1 1 1 
1 1 2 
1 1 3 
1 1 4 
1 1 5 
1 2 1 
1 2 2 
1 2 3 
…
5 5 4 
5 5 5