C++で指定した長さのすべての数列（順列）を出力する方法

この問題では、2つの整数 k と n が与えられます。そして、1からnまでの数字を使って、長さkのすべての数列をソートされた順序で出力することが求められます。

具体例を見てみましょう。

入力：k = 2 ; n = 3
出力：
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

つまり、この問題では上記のように、条件を満たすすべての数列を出力する必要があります。

解法1：繰り返しによるアプローチ

最もシンプルな解き方は、数列の各要素をインクリメントしていき、最大値nに達するまで繰り返すというものです。以下に詳しく説明します。

アルゴリズム

1) サイズkの配列を作成し、すべての値を1で初期化する（{1, 1, ...}）。
2) 配列が {n, n, ..., n} になるまで、ステップ3と4を繰り返す。
3) 配列の内容を出力する。
4) 次の値へと要素を更新する。例えば {1, 1, 1} は {1, 1, 2} へ、{1, 3, 3} は {2, 1, 1} へと変化する。
   この処理のためには、配列の末尾（k番目）の要素がnと等しいかどうかを確認し、
   等しい場合はその前の要素（k-1番目）を確認する、という操作を繰り返す必要がある。

実装例

次のプログラムを見ると、この概念がより明確になります。

#include<iostream>
using namespace std;
void printSequence(int arr[], int size){
    for(int i = 0; i < size; i++)
        cout<<arr[i]<<"\t";
    cout<<endl;
    return;
}
int nextElement(int arr[], int k, int n){
    int s = k - 1;
    while (arr[s] == n)
        s--;
    if (s < 0)
        return 0;
    arr[s] = arr[s] + 1;
    for(int i = s + 1; i < k; i++)
        arr[i] = 1;
    return 1;
}
void generateSequence(int n, int k){
    int *arr = new int[k];
    for(int i = 0; i < k; i++)
        arr[i] = 1;
    while(1){
        printSequence(arr, k);
        if(nextElement(arr, k, n) == 0)
            break;
    }
    return;
}
int main(){
    int n = 3;
    int k = 2;
    cout<<"The sequence is :\n";
    generateSequence(n, k);
    return 0;
}

出力結果

出力は以下の通りです。

The sequence is :
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

この手法は理解しやすいのですが、より効率的な方法に改善できます。

解法2：再帰によるアプローチ

こちらの手法では再帰と追加のインデックスを使用して、数列のオフセット（桁が切り替わる位置）を管理します。関数は再帰的に呼び出され、そのインデックスまでは値を更新せず、インデックス以降の項に対して再帰処理を行います。

実装例

#include<iostream>
using namespace std;
void printSequence (int arr[], int size){
    for (int i = 0; i < size; i++)
        cout << arr[i] << "\t";
    cout << endl;
    return;
}
void generateSequence (int arr[], int n, int k, int index){
    int i;
    if (k == 0){
        printSequence (arr, index);
    }
    if (k > 0){
        for (i = 1; i <= n; ++i){
            arr[index] = i;
            generateSequence (arr, n, k - 1, index + 1);
        }
    }
}
int main (){
    int n = 3;
    int k = 2;
    int *arr = new int[k];
    cout<<"The sequence is:\n";
    generateSequence (arr, n, k, 0);
    return 0;
}

出力結果

出力は以下の通りです。

The sequence is:
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

まとめ

繰り返しを使う方法は直感的で分かりやすい一方、再帰を使う方法はコードが簡潔になり、深さ優先探索のような構造で自然にすべての組み合わせを生成できます。どちらの手法も計算量はO(n^k)となり、生成すべき数列の総数に比例します。用途や可読性の要件に応じて、適切な方を選択するとよいでしょう。