C++でk個のピークを持つ順列を構築するプログラム

2つの整数 n と k が与えられたとします。このとき、1から n までの数字をすべて使って構成し、ちょうど k 個のピーク（山）を持つ順列 A を作成する必要があります。

ここで、配列 A のインデックス i が「ピーク」であるとは、次の条件を満たすことを指します。

A[i] > A[i-1] かつ A[i] > A[i+1]

つまり、隣接する両側の要素よりも大きい要素がピークとなります。もし条件を満たす順列が存在しない場合は、-1 を返します。

例として、n = 5、k = 2 が入力された場合、出力は [2, 4, 1, 5, 3] のようになります（これ以外の答えも存在します）。

アルゴリズムの手順

この問題は、以下の手順で解くことができます。

k > (n - 1) / 2 の場合：
    return -1
サイズ101の配列 a を定義する。
i := 1 から i <= n まで、i を1ずつ増やしながら繰り返す：
    a[i] := i
i := 2 から i <= 2 * k まで、i を2ずつ増やしながら繰り返す：
    a[i] と a[i + 1] を入れ替える
i := 1 から i <= n まで、i を1ずつ増やしながら繰り返す：
    a[i] を出力する

アルゴリズムのポイント

まず、ピークの最大数に注目しましょう。長さ n の順列で作れるピークの最大数は (n - 1) / 2 です。これは、各ピークの前後に必ず小さい要素が必要になるためです。したがって、k がこの値を超える場合は構築不可能となり、-1 を返します。

構築可能な場合の戦略はシンプルです。最初に 1, 2, ..., n という昇順の並びを作り、偶数番目の位置にある要素をその隣の要素と入れ替えていきます。この操作を k 回行うことで、ちょうど k 個のピークを持つ順列が得られます。

C++での実装例

理解を深めるために、実際の実装を見てみましょう。

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

void solve(int n, int k) {
    if (k > (n - 1) / 2) {
        cout << "-1";
        return;
    }
    int a[101];
    for (int i = 1; i <= n; i++)
        a[i] = i;
    for (int i = 2; i <= 2 * k; i += 2) {
        swap(a[i], a[i + 1]);
    }
    for (int i = 1; i <= n; i++)
        cout << a[i] << ", ";
}
int main() {
    int n = 5;
    int k = 2;
    solve(n, k);
}

入力

5, 2

出力

1, 3, 2, 5, 4,

この出力では、インデックス2の「3」とインデックス4の「5」がそれぞれ両隣より大きいため、2つのピークが存在することが確認できます。

計算量について

このアルゴリズムの時間計算量は O(n)、空間計算量も O(n) であり、非常に効率的です。入れ替え処理は最大でも k 回しか発生せず、全体としては配列の初期化と出力が支配的になります。