C++で式の結果がちょうど2Kになる2N個の自然数の順列を見つける方法

2つの整数 N と K が与えられたとき、次の式を満たすような「2N個の自然数の順列」を見つける問題を考えてみましょう。

Σ(i=1〜N) |A[2i−1] − A[2i]| + |Σ(i=1〜N) (A[2i−1] − A[2i])| = 2K

ここで、K の値は N 以下でなければなりません。たとえば N = 4、K = 1 の場合、出力は「2 1 3 4」になります。この順列に対する式の値は、(|2−1| + |3−4|) + |2−1+3−4| = 2 となり、条件どおり 2K = 2 を満たします。

アルゴリズムの基本的な考え方

発想はとてもシンプルです。まず「1, 2, 3, 4, 5, 6, …」のようにソートされた数列を用意します。この数列に対して、隣接するペア(2i−1 番目と 2i 番目)を入れ替えるたびに、式の結果は必ずちょうど 2 ずつ増加します。したがって、この入れ替えを K 回行えば、最終的な結果は 2K になります。

C++による実装例

以下のコードでは、i 番目のペアについて、i が K 以下であれば「2i, 2i−1」の順(入れ替えあり)で、そうでなければ「2i−1, 2i」の順(そのまま)で出力します。

#include <iostream>
using namespace std;

void showPermutations(int n, int k) {
    for (int i = 1; i <= n; i++) {
        int a = 2 * i - 1;
        int b = 2 * i;
        if (i <= k)
            cout << b << " " << a << " ";
        else
            cout << a << " " << b << " ";
    }
}

int main() {
    int n = 4, k = 2;
    showPermutations(n, k);
    return 0;
}

実行結果

2 1 4 3 5 6 7 8

この例では N = 4、K = 2 であるため、最初の 2 つのペア(1, 2)と(3, 4)が入れ替えられ、残りの(5, 6)と(7, 8)は元の順序のまま出力されています。その結果、式の値はちょうど 2K = 4 となります。

計算量

このアルゴリズムは数列を一度走査するだけで答えを構築できるため、時間計算量は O(N) です。また、追加の配列なども不要で、空間計算量は O(1) に抑えられます。