最初のN個の自然数の「良い順列」をC++で求める方法

この問題では、整数値 N が与えられ、最初のN個の自然数の「良い順列(good permutation)」を見つけることが課題となります。

順列とは、あるオブジェクトの集合の全部または一部を、並べる順序を考慮して並べたもののことです。

良い順列とは、1 ≤ i ≤ N を満たすすべての i について、次の条件を満たす順列を指します。

P[P[i]] = i

つまり、順列を2回適用すると元の値に戻るという性質(自己逆順列)を持つ必要があります。

例で問題を理解する

入力 : N = 1
出力 : -1

N = 1 の場合、条件を満たす順列が存在しないため、-1 を出力します。

解法アプローチ

この問題に対するシンプルな解法は、p[i] ≠ i となるような順列 p を構成することです。

具体的には、2x ≤ N を満たす各値 x に対して、p[2x−1] = 2x、p[2x] = 2x−1 と定めます。これは、隣り合う2つの要素を順に入れ替えていく操作に相当します。

このように構成すると、すべての i について P[P[i]] = i が成立するため、条件を満たす順列が得られます。一方、N が奇数の場合は必ず1つの要素がペアを持てず、良い順列が存在しないため、-1 を出力します。

実装例

以下は、この解法の動作を示すC++プログラムです。

#include <iostream>
using namespace std;

void printGoodPermutation(int n) {
    if (n % 2 != 0)
        cout << -1;
    else
        for (int i = 1; i <= n / 2; i++)
            cout << (2*i) << "\t" << ((2*i) - 1) << "\t";
}

int main() {
    int n = 4;
    cout << "Good Permutation of first N natural Numbers : \n";
    printGoodPermutation(n);
    return 0;
}

出力

Good Permutation of first N natural Numbers :
2 1 4 3

動作の解説

N = 4 の場合、出力される順列は「2 1 4 3」です。この順列が条件を満たしているか確認してみましょう。

• P[1] = 2、P[2] = 1 → P[P[1]] = P[2] = 1(条件を満たす)
• P[3] = 4、P[4] = 3 → P[P[3]] = P[4] = 3(条件を満たす)

このように、すべての i について P[P[i]] = i が成立していることがわかります。

計算量

• 時間計算量: O(N) — 1回のループで順列を出力します。
• 空間計算量: O(1) — 追加の配列は不要です。