配列の k 回転

1 個ずつずらすと、k が大きいときに終わらない

「右に 1 つずらす」を k 回繰り返せば答えは出ます。長さ 5 の配列を 2 回まわすだけなら、それで十分です。ところが k に 10^9 が来た瞬間、この素朴な実装は O(n * k) になって帰ってきません。

先に気づくべきなのは、長さ 5 の配列を 7 回まわした結果が、2 回まわした結果とまったく同じだという点です。1 周ぶんの回転は、何もしていないのと変わりません。だから k はそのまま使わず、n で割った余りに畳んでから使います。

days = ["月", "火", "水", "木", "金", "土", "日"]
days[(2 + 100) % 7]   # 水曜の 100 日後の曜日

曜日を 100 日ぶん進めるとき、100 回ループを回す人はいません。配列の回転も同じ発想です。

「右に k 回す」を、完成形から見直す

回転を「1 つずらす操作の繰り返し」と捉えている限り、ループの外へ出られません。先に完成形を見てしまうのが早道です。

[1, 2, 3, 4, 5] を 2 回まわすと [4, 5, 1, 2, 3] になります。並びをよく見てください。[4, 5] も [1, 2, 3] も、元の順序のまま崩れずに残っています。動いたのは、この 2 つのかたまりの前後関係だけです。

ここまで言い換えられれば、何回まわすかという話は消えて、どこで切るかという話になります。切る位置を決めるのに使うのが、さきほどの余りです。

なお、切り出して繋ぎ直すやり方は新しい配列を 1 本ぶん作るので、メモリを O(n) 使います。追加のメモリをほとんど使わずに済ませたい場面では、reverse を何度か組み合わせて同じ並びに持っていく手も知られています。ただしそちらは元の配列をその場で書き換える前提です。

どちらを選ぶかは速さではなく、元の配列を壊してよいかで決まります。今回は残す必要があるので、新しい配列を返す側で考えてください。実務でも、呼び出し元が渡した配列が知らないうちに書き換わっているのは、追いにくいバグの代表格です。

n が 0 のときだけ、別の壊れ方をする

k % n は便利ですが、n が 0 だと割り算そのものが例外になります。空配列は「何回まわしても空配列」なので、余りを取る前に片付けておくのが安全です。k が 0 のときも、余計な処理を挟まずそのまま返せます。

境界が 2 つあるときは、どちらを先に弾くかで書きやすさが変わります。空配列を先に返してしまえば、その後の行では長さが 1 以上であることを前提にできるので、条件がひとつ減ります。

テストで確かめるべきは、k が長さちょうどのとき、長さより大きいとき、0 のとき、そして要素が 1 個だけのときです。この 4 つが通れば、真ん中あたりの値はまず外しません。

やってみよう

ひな形の TODO を完成させてください。一周を除く計算と、切断した前後の連結を自分で書きます。入力を受け取る枠と説明つきの準備部分はそのまま使えます。

演習で使う書き方

本文の曜日の例では一周する回数を余りで取り除きます。配列の右回転も同じです。items[cut:] は cut 以降、items[:cut] は cut より前、配列の + は連結です。空配列の処理と長さだけを用意し、余り・切断位置・前後の連結を自分で書きます。

1. 一周を除く計算と、切断した前後の連結を自分で実装する
2. 関数名と引数、入力と戻り値の形を保つ。説明つきの準備部分を使い、TODO の仮の処理を置き換える