最初のN個の自然数を、隣接要素間の絶対差が1より大きくなるように並べ替えるには？

問題の概要

1からNまでの最初のN個の自然数が与えられます。この中から、隣接する2つの要素の絶対差がすべて1より大きくなるような順列を1つ求めるのが課題です。そのような順列が存在しない場合は -1 を返します。

解き方のアプローチ

この問題は貪欲法（グリーディアルゴリズム）を使うことで簡単に解けます。考え方は次の通りです。

• まず、すべての奇数を降順（または昇順）に並べます。奇数同士は必ず2以上離れているため、隣接要素間の絶対差は1より大きくなります。
• 次に、すべての偶数を降順（または昇順）に並べます。こちらも偶数同士の差は2以上あるため条件を満たします。
• 境界部分では、最小の奇数「1」と最大の偶数が隣接しますが、この差も必ず1より大きいため、全体として条件を満たす順列が得られます。

なお、Nが2または3の場合はどのように並べても隣接要素の差が1になる箇所が現れるため、条件を満たす順列は存在しません。

アルゴリズム

arrangeN(n)

Begin
   N が 1 の場合、1 を出力して終了
   N が 2 または 3 の場合、条件を満たす順列が存在しないため -1 を返す
   even_max と odd_max に、n 以下の最大の偶数・奇数を設定する
   すべての奇数を降順に出力する
   すべての偶数を降順に出力する
End

C++による実装例

#include <iostream>
using namespace std;
void arrangeN(int N) {
   if (N == 1) { // N が 1 の場合、その数のみを出力
      cout << "1";
      return;
   }
   if (N == 2 || N == 3) { // N = 2, 3 の場合は条件を満たす順列なし
      cout << "-1";
      return;
   }
   int even_max = -1, odd_max = -1;
   // N 以下の最大の偶数と奇数を求める
   if (N % 2 == 0) {
      even_max = N;
      odd_max = N - 1;
   } else {
      odd_max = N;
      even_max = N - 1;
   }
   while (odd_max >= 1) { // 奇数を降順で出力
      cout << odd_max << " ";
      odd_max -= 2;
   }
   while (even_max >= 2) { // 偶数を降順で出力
      cout << even_max << " ";
      even_max -= 2;
   }
}
int main() {
   int N = 8;
   arrangeN(N);
}

実行結果

7 5 3 1 8 6 4 2

N = 8 の場合、出力は「7 5 3 1 8 6 4 2」となります。隣接要素間の差はそれぞれ 2, 2, 2, 7, 2, 2, 2 であり、すべて1より大きいことが確認できます。

計算量

• 時間計算量： O(N) ― 各数値を一度だけ出力するため。
• 空間計算量： O(1) ― 追加の配列などは不要。