【C++】nから始まり隣接要素の差がk未満となるすべての数列を出力する方法

問題の概要

この問題では、3つの変数 n(開始値)、s(数列の長さ)、k(差の上限)が与えられます。求めるのは、「数 n から始まり、長さ s を持ち、隣り合う要素どうしの絶対差が k 未満である」ような、考えられるすべての数列を出力することです。

入力例と出力例

まずは具体例を見ながら、問題をより深く理解しましょう。

Input: n = 3, s = 3, k = 2
Output:
3 3 3
3 3 4
3 3 2
3 4 4
3 4 5
3 4 3
3 2 2
3 2 3
3 2 1

この例では、先頭が 3 で始まる長さ 3 の数列のうち、隣接する要素の絶対差が 2 未満(つまり 0 または 1)になっているものがすべて列挙されています。

解法のアプローチ

この問題のポイントは、隣接要素間の絶対差を k 未満に抑える必要がある点です。そのためには、次の要素として「現在の値より大きい値(正の差)」と「現在の値より小さい値(負の差)」の両方を候補として生成します。

具体的な手順は以下のとおりです。

• n から開始し、各位置の要素に対して再帰呼び出しを行います。
• 0 から k-1 までのループで、現在の数値に加算した値を次の要素の候補とします(正方向)。
• 同様に、1 から k-1 まで減算した値も候補とします(負方向)。

このように再帰とバックトラッキングを組み合わせることで、条件を満たすすべての数列を網羅的に列挙できます。

C++での実装例

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

void printConsecutiveNumbers(vector<int>& v, int n, int s, int k){
    // 長さ s の数列が完成したら出力する
    if (s == 0) {
        for (int i = 0; i < v.size(); i++)
            cout << v[i] << " ";
        cout << endl;
        return;
    }
    // 正方向:現在の値に 0 ~ k-1 を加えた候補を試す
    for (int i = 0; i < k; i++) {
        v.push_back(n + i);
        printConsecutiveNumbers(v, n + i, s - 1, k);
        v.pop_back(); // バックトラッキング
    }
    // 負方向:現在の値から 1 ~ k-1 を引いた候補を試す
    for (int i = 1; i < k; i++) {
        v.push_back(n - i);
        printConsecutiveNumbers(v, n - i, s - 1, k);
        v.pop_back(); // バックトラッキング
    }
}

int main(){
    int n = 3, s = 3, k = 2;
    cout << "The sequence is :\n";
    vector<int> v;
    v.push_back(n); // 先頭に n を設定
    printConsecutiveNumbers(v, n, s - 1, k);
    return 0;
}

コードの解説

printConsecutiveNumbers 関数は、残りの要素数 s が 0 になった時点で、ベクトルに格納された数列を出力して処理を終了します(再帰の基底ケース)。それ以外の場合は、正方向(n + i)と負方向(n - i)の両方について再帰的に探索を行い、push_back と pop_back によるバックトラッキングで状態を元に戻しながら、条件を満たすすべての組み合わせを列挙します。

なお、このアルゴリズムの時間計算量は、各ステップで最大 2k-1 通りの候補を生成するため、おおよそ O((2k−1)^s) となります。s や k が大きくなると組み合わせ数が急増する点に注意してください。

実行結果

上記のコードを実行すると、次の出力が得られます。

The sequence is :
3 3 3
3 3 4
3 3 2
3 4 4
3 4 5
3 4 3
3 2 2
3 2 3
3 2 1

期待どおり、3 から始まり長さ 3、隣接要素の絶対差が 2 未満となるすべての数列が出力されていることが確認できます。