C++で指定された条件を満たす最初のN個の自然数の順列を求めるアルゴリズム

2つの整数 N と K が与えられたとき、最初の N 個の自然数からなる順列 P のうち、すべての 1 ≤ i ≤ N に対して GCD(P[i], i) > 1 を満たす要素がちょうど K 個になるような順列を求める問題を考えてみましょう。

例えば、N = 3、K = 1 の場合、答えは「2, 1, 3」になります。実際に確認すると、gcd(2, 1) = 1、gcd(1, 2) = 1、gcd(3, 3) = 3 となり、条件を満たす要素は1つだけであることがわかります。

解法のアプローチ

この問題の解法は非常にシンプルです。末尾の K 個の要素は元の位置にそのまま残し、残りの要素を1つずつ後ろにずらします。具体的には、i 番目の要素を (i + 1) 番目の位置へ移動させ、(N − K) 番目の要素を先頭（1番目）の位置に配置します。

これがうまく機能する理由は、隣り合う整数の最大公約数は必ず1になる（gcd(x, x+1) = 1）という性質によるものです。ずらされた部分では条件を満たす要素が生じず、そのまま残した末尾の K 個の要素のみが gcd(P[i], i) = i > 1 を満たすため、ちょうど K 個という要件を達成できます。

サンプルコード

#include<iostream>
using namespace std;

void findPermutation(int n, int k) {
    int permutation[n + 1];
    // 初期状態として permutation[i] = i を設定
    for (int i = 1; i <= n; i++)
        permutation[i] = i;
    // 先頭側の要素を1つ後ろへずらす
    for (int i = 1; i < n - k; i++)
        permutation[i + 1] = i;
    // (N - K) 番目の値を先頭に配置
    permutation[1] = n - k;
    // 結果の出力
    for (int i = 1; i <= n; i++)
        cout << permutation[i] << " ";
}

int main() {
    int n = 5, k = 2;
    cout << "The permutation is: ";
    findPermutation(n, k);
}

実行結果

The permutation is: 3 1 2 4 5

出力「3 1 2 4 5」を検証してみると、gcd(3, 1) = 1、gcd(1, 2) = 1、gcd(2, 3) = 1 であり、条件を満たすのは gcd(4, 4) = 4 と gcd(5, 5) = 5 の2箇所だけです。つまり K = 2 の要件を正確に満たしていることが確認できます。

このアルゴリズムの計算量は O(N) であり、配列を一度走査するだけで順列を構築できるため、非常に効率的です。