C++で最初のn個の自然数から長さkの増加列をすべて出力する方法

この問題では、2つの整数 K と n が与えられます。求められているのは、最初の n 個の自然数を使って作れる長さ K の増加列をすべて出力することです。

増加列とは

増加列（増加シーケンス）とは、隣り合う要素において、次の要素の値が必ず前の要素より大きくなっている数列のことです。

具体例で問題を確認してみましょう。

入力：n = 4, K = 2
出力：
1 2
1 3
1 4
2 3
2 4
3 4

解法のアプローチ

この問題は、バックトラッキング（再帰）を使うことで効率的に解けます。基本的な考え方は以下の通りです。

• 現在生成中のシーケンスを保持するための、長さ k の配列を用意します。
• 配列の各位置について、直前に置いた要素を参照し、それより大きい値だけを次の候補として選びます。
• 先頭の位置には 1 から n までの値を順番に固定しながら、再帰的に残りの位置を埋めていきます。

この方法により、重複のない増加列だけを網羅的に生成できます。

C++での実装例

上記のロジックを実装したプログラムがこちらです。

#include<iostream>
using namespace std;

// 生成されたシーケンスを出力する関数
void printSequence(int arr[], int k) {
    for (int i = 0; i < k; i++)
        cout << arr[i] << " ";
    cout << endl;
}

// 長さ k の増加列を再帰的に生成する関数
void printKLengthSequence(int n, int k, int &len, int arr[]) {
    // シーケンスの長さが k に達したら出力
    if (len == k) {
        printSequence(arr, k);
        return;
    }
    // 先頭位置なら 1 から、それ以外は前の要素 + 1 から開始
    int i = (len == 0) ? 1 : arr[len - 1] + 1;
    len++;
    while (i <= n) {
        arr[len - 1] = i;
        printKLengthSequence(n, k, len, arr);
        i++;
    }
    len--; // バックトラッキング
}

void generateSequence(int n, int k) {
    int arr[k];
    int len = 0;
    printKLengthSequence(n, k, len, arr);
}

int main() {
    int k = 3, n = 4;
    cout << "最初の " << n << " 個の自然数から生成される長さ " << k << " のシーケンス：\n";
    generateSequence(n, k);
    return 0;
}

実行結果

最初の 4 個の自然数から生成される長さ 3 のシーケンス：
1 2 3
1 2 4
1 3 4
2 3 4

計算量について

このアルゴリズムが生成するシーケンスの総数は、n 個の中から k 個を選ぶ組み合わせの数、すなわち C(n, k) に等しくなります。そのため時間計算量は O(C(n, k) × k) となります。使用する補助配列は長さ k 分のみなので、空間計算量は O(k) です。