C++で最初のN個の数字をKの距離になるように並べ替える方法

問題概要

整数 N と K が与えられたとき、まず 1 から N までの順列を作成し、その後、すべての要素が元の位置からちょうど K だけ離れるように並べ替えることを考えます。

入出力のシナリオ例

入力 − int n = 20, int k = 2

出力 − 最初のN個の数字をK距離に並べ替えた結果： 3 4 1 2 7 8 5 6 11 12 9 10 15 16 13 14 19 20 17 18

説明 − 整数 N = 20、K = 2 が与えられています。まず順列 1, 2, 3, ..., 20 を作成し、続いて各要素が元の位置からちょうど「k」の距離に配置されるように並べ替えます。たとえば先頭の「3」は元の位置（3番目）から2つ移動していることがわかります。

入力 − int n = 10, int k = 3

出力 − Not Possible（不可能）

説明 − 整数 N = 10、K = 3 が与えられています。順列 1 〜 10 を作成し、各要素をKの距離に配置しようとしますが、この入力値の組み合わせでは条件を満たす並べ替えは存在しません。

なぜ「N が 2×K の倍数」である必要があるのか

この問題では、配列を 2K 個ずつのブロックに分割し、各ブロック内で前半 K 個と後半 K 個を入れ替えることで、すべての要素をちょうど K 移動させています。入れ替えの単位が 2K 個であるため、N が 2×K で割り切れない場合、余りの要素をどう配置しても条件を満たせず、「Not Possible」となります。

プログラムのアプローチ

• 整数型の入力として「N」と「K」を受け取ります。

• N と K を引数として関数 Rearrangement(int n, int k) を呼び出します。

• 関数 Rearrangement(int n, int k) の内部では、次の処理を行います。

  • 整数変数 temp を宣言し、n % (2 * k) の値を代入します。

  • サイズ n + 1 の整数型配列 ptr[n+1] を宣言します。

  • k == 0 の場合は並べ替えが不要のため、i を 1 から n までループしてそのまま出力します。

  • temp != 0 の場合は「Not Possible」を出力して終了します。

  • i を 1 から n までループし、ptr[i] に i を代入して順列を初期化します。

  • i を 1 から n まで 2 * k ずつ増やしながらループし、内側で j を 1 から k までループさせながら swap(ptr[i + j - 1], ptr[k + i + j - 1]) を呼び出して要素を入れ替えます。

  • 最後に i を 1 から n までループして ptr[i] を出力します。

• 結果を出力します。

実装例（C++）

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

// 最初のN個の数字をK距離になるように並べ替える関数
void Rearrangement(int n, int k){
    int temp = n % (2 * k);
    int ptr[n + 1];
    // k が 0 の場合は並べ替え不要
    if(k == 0){
        for(int i = 1; i <= n; i++){
            cout << i << " ";
        }
        return;
    }
    // N が 2*k で割り切れない場合は不可能
    if(temp != 0){
        cout<<"Not Possible";
        return;
    }
    // 順列の初期化
    for(int i = 1; i <= n; i++){
        ptr[i] = i;
    }
    // 2k 個ごとのブロックで前半 k 個と後半 k 個を入れ替える
    for(int i = 1; i <= n; i += 2 * k){
        for(int j = 1; j <= k; j++){
            swap(ptr[i + j - 1], ptr[k + i + j - 1]);
        }
    }
    // 結果の出力
    for(int i = 1; i <= n; i++){
        cout << ptr[i] << " ";
    }
}
int main(){
    int n = 20;
    int k = 2;
    cout<<"最初のN個の数字をK距離に並べ替えた結果: ";
    Rearrangement(n, k);
    return 0;
}

実行結果

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

最初のN個の数字をK距離に並べ替えた結果: 3 4 1 2 7 8 5 6 11 12 9 10 15 16 13 14 19 20 17 18

まとめ

このアルゴリズムの計算量は O(N) であり、配列を一度走査するだけで並べ替えが完了します。ポイントは「N が 2×K で割り切れること」を事前に判定することです。この条件を満たさない場合は解が存在しないため、無駄な処理を行う前に早期に「Not Possible」を返す設計になっています。K = 0 の場合などエッジケースも忘れずに扱うことで、堅牢な実装になります。