配列を「左に k 個ぶん回したい」場面があります。

[A, B, C, D, E, F, G] を 2 つ左に回すと [C, D, E, F, G, A, B]。先頭の何個かが、そっくり後ろへ回り込むイメージです。リングバッファ 、文字列のローテーション、表示行の巻き戻し——地味ですがよく出てきます。

素直にやるなら、回したあとの並びを別の配列に書き出して、それで元を置き換えれば終わりです。ただ、それだと配列がもう1本ぶん、まるごとメモリに要ります。動かしたいのは「順番」だけなのに、です。

この記事では、別配列を一切使わず、その場（in-place）で配列を回す方法を2つ紹介します。3回ひっくり返すだけのリバーサル法と、$\gcd(n,k)$ 本の鎖で穴を歩かせるジャグリング法。最後に、両方をブラウザだけで動くビジュアライザで実際に触って確かめます。

この記事は、画像をリネームだけで並び替える「玉突き方式」 の続編にあたります。あちらで出てきた「穴を歩かせる」手口が、今回のジャグリング法でそのまま効いてきます。

まず、素朴なやり方とその代償

いちばん分かりやすいのは、結果を別配列へ書くやり方です。

function rotateLeftCopy(a, k){
  const n = a.length;
  k = ((k % n) + n) % n;   // 負の k も正の回転量に正規化
  const out = new Array(n);
  for(let i = 0; i < n; i++){
    out[i] = a[(i + k) % n];   // マス i には「元の (i+k) 番目」が来る
  }
  return out;
}

これは正しく動きます。ただ、out という長さ $n$ の別配列が要ります。要素が重かったり本数が多かったりすると、この「もう1本」が効いてきます。

やりたいのは並べ替えだけ。中身は1つも変わりません。だったら、追加メモリ $O(1)$（作業用の変数1個ぶん）で済ませたい。ここからが本題です。

方法1：リバーサル法（3回ひっくり返すだけ）

最初に紹介するのは、拍子抜けするほど単純な方法です。左回転 k は、次の3回の部分反転に分解できます。

  1. 前半 k 個を反転する
  2. 後半 n−k 個を反転する
  3. 全体を反転する

[A, B, C, D, E, F, G] を k=2 で左に回す例で追ってみます。

初期:        A B C D E F G
① 前半2個反転: B A C D E F G
② 後半5個反転: B A G F E D C
③ 全体を反転:  C D E F G A B   ← 完成（左に2回した結果）

最後の ③ 全体を反転 で、ちゃんと [C, D, E, F, G, A, B] に揃いました。

なぜこれで合うのか。配列を「前半の塊 $X$」と「後半の塊 $Y$」に分けて考えると見えてきます。欲しい結果は $Y$ のあとに $X$ が来た $YX$ です。①②でそれぞれの塊を内部だけ反転して $X^{R} Y^{R}$ にし、③で全体を反転すると $(X^{R} Y^{R})^{R} = Y X$。反転を二重にかけると塊の中身は元に戻り、塊どうしの順番だけが入れ替わる——これがからくりです。

反転そのものは、両端から1組ずつスワップしていくだけ。追加で要るのは交換用の変数1個だけなので、メモリは $O(1)$ です。

function reverse(a, l, r){
  while(l < r){ [a[l], a[r]] = [a[r], a[l]]; l++; r--; }
}
function rotateLeftReverse(a, k){
  const n = a.length; k = ((k % n) + n) % n;
  reverse(a, 0, k - 1);     // ① 前半
  reverse(a, k, n - 1);     // ② 後半
  reverse(a, 0, n - 1);     // ③ 全体
  return a;
}

実装の短さがこの方法のいちばんの取り柄です。

方法2：ジャグリング法（穴を歩かせる）

もう1つは、玉突き記事と地続きの方法です。

左回転とは、要するに「すべての要素を k マスぶん前へ送る」こと。マス $i$ にいた要素は、最終的にマス $(i-k+n) \bmod n$ へ行きます。これを玉突きと同じ要領で、穴を歩かせて実現します。

  1. 先頭の1枚を作業用の temp へ逃がす。そこに穴が空く。
  2. 今ある穴に、穴から見て k 先の要素を引いてくる。引いた跡地が次の穴になる。
  3. これを繰り返すと、穴が一定間隔（k おき）で配列をぐるりと一周する。一周して戻ったら temp を最後の穴へ戻す。

ここで面白いのが、一周しても全部は埋まらないことがある点です。k おきに飛んでいくので、$n$ と $k$ の相性によっては、同じ何マスかだけをぐるぐる回って出発点に戻ってきてしまう。そこで、まだ触っていないマスを起点にもう1周……と繰り返します。

この周回の本数が、ちょうど $\gcd(n, k)$ 本になります。たとえば $n=8, k=2$ なら $\gcd(8,2)=2$ で、偶数マスの鎖と奇数マスの鎖の2本。$n=7, k=2$ なら $\gcd(7,2)=1$ で、ぜんぶが1本の長い鎖につながります。玉突き記事で「並び替えがいくつのサイクルに分かれるか」を数えたのと、まったく同じ構造です。

function gcd(a, b){ while(b){ [a, b] = [b, a % b]; } return a; }

function rotateLeftJuggle(a, k){
  const n = a.length; k = ((k % n) + n) % n;
  if(k === 0) return a;
  const cycles = gcd(n, k);            // 周回の本数
  for(let s = 0; s < cycles; s++){
    const temp = a[s];                 // 先頭を退避 ＝ 穴ができる
    let j = s;
    while(true){
      const d = (j + k) % n;           // 穴から見て k 先
      if(d === s) break;               // 一周して戻った
      a[j] = a[d];                     // k 先の要素を穴へ
      j = d;                           // 穴が d へ歩く
    }
    a[j] = temp;                       // 最後に temp を戻す
  }
  return a;
}

リバーサル法が「塊ごとひっくり返す」のに対し、ジャグリング法は1つ1つの要素を最終位置へ直接運ぶ。動いた要素は一度置いたら二度と動きません。玉突き方式の「穴に入った画像はそのまま最終位置」と同じ気持ちよさです。

玉突きとの関係——同じアルゴリズムだった

実はジャグリング法は、玉突き記事の「サイクルを巡回して並び替える」手続きとまったく同じものです。違うのは、サイクルの見つけ方だけ。

玉突きでは並び替えが任意だったので、perm[] を辿って鎖を発見し、どこを訪れたかを覚えておく必要がありました。ところが回転では、鎖の本数が $\gcd(n,k)$ 本・間隔が k と最初から分かっています。だから探す手間も、訪問済みの記帳も要りません。

一般の手続きに「回転」という特別な構造が加わると、記帳がまるごと消える——これが玉突きとの一番おもしろい接点です。回転は、玉突きで扱った「任意の並び替え」のうち、最も構造の整った1ケースだった、というわけです。

どちらを使うか

両方とも追加メモリ $O(1)$ で、計算量も $O(n)$。甲乙つけがたいので、性格の違いで選びます。

  • リバーサル法：実装が最短。各要素はならすと2回動きます（反転を二重にかけるぶん）。キャッシュに乗りやすく、現場ではこちらが好まれがちです。
  • ジャグリング法：各要素をちょうど1回だけ動かして最終位置へ運ぶので、移動回数は最小。ただし $k$ おきに飛ぶアクセスがメモリ上で散らばりやすく、鎖の本数（$\gcd(n,k)$）を意識する必要があります。

「移動回数だけ」で見ればジャグリングが少なく、「実装の素直さと実機での速さ」で見ればリバーサルが優勝、というのが正直なところです。

触ってみる

ここまでの話を、実際に動かして確かめられるようにしました。下のビジュアライザを触ってみてください。

  • 上の方式を「リバーサル／ジャグリング」で切り替えると、同じ回転での運び方の違いがそのまま見えます。
  • スライダーで 要素数 n と 回す量 k を変えられます。ジャグリングのときは、$\gcd(n,k)$ が変わると周回の本数（鎖の数）が変わる様子を確かめてみてください。
  • 「最初から再生」で1ステップずつ自動再生。リバーサルでは反転中の範囲が青く、ジャグリングでは temp・穴・確定（緑枠）が見えます。

うまく表示されないときは、ビジュアライザを別タブで開く 。

ここでは踏み込まない点

  • 右回転。左に k 回すのは、右に $n-k$ 回すのと同じです。どちらか一方を実装すれば、引数を変えるだけで両方まかなえます。
  • k が n を超える・負になる場合。k % n で畳めば同じ回転に帰着します（負は $((k \bmod n) + n) \bmod n$ で正に直します）。本文のコードはこの正規化を入れてあります。
  • 要素が重い場合の代入コスト。ここでは「代入は1手」と数えました。実際には1要素のコピーが重いと、移動回数の差がそのまま効いてきます。

まとめ

  • 配列の左回転は、別配列にコピーしなくてもその場（追加メモリ $O(1)$）でできる。
  • リバーサル法は「前半・後半・全体」を反転する3ステップ。実装が最短で、実機でも速い。
  • ジャグリング法は穴を歩かせて各要素を最終位置へ直接運ぶ。周回の本数はちょうど $\gcd(n,k)$ 本で、玉突き方式とまったく同じ「サイクルを歩く」構造。
  • 移動回数だけならジャグリングが最小、素直さと速さならリバーサル。場面で選べばよい。

理屈だけだとピンと来にくいので、ぜひ上のビジュアライザで n と k を動かしながら、塊がひっくり返る様子と、穴が k おきに歩く様子を見比べてみてください。