Pythonアルゴリズム

Pythonでリストを回転させる

このレッスンでは、スライスを使ってリストを右にk個ぶん回転させます。

  • 中級
  • 約2分で読めます
  • 実行できるサンプル 1 件

はじめに

どんな問題を解決するか

リストの回転は、当番表(次は誰の番か)、循環バッファー、画像の処理、面接問題などに出てきます。1ステップずつ要素を動かすと遅いですが、スライスなら1回でできます。

身近なたとえ

リストの回転は、全員が右に2席ずつずれる円卓のようなものです。最後の2人が回って最初の席に着き、ほかの人は順番を保ちます。席の数ちょうどだけ回転しても何も変わりません。

円卓からコードへ
steps %= len(values)🔁 5席のテーブルで7席動くのは2席と同じ
values[-steps:]🚶 最後の2人が前へ移る
values[:-steps]🪑 ほかの人は順番を保つ
+🔗 一緒に座らせる:[4, 5, 1, 2, 3]
リストを2つに切り、入れ替えます。
ひと言でいうと

リストを右に k だけ回転すると、最後の k 個の要素が前に移り、すべての要素の順番は保たれます。

重要なポイント

  1. if not values: return [] は空のリストを処理します。そうしないと % len(values) が0で割ることになります。
  2. steps %= len(values) は大きな回転数を折り返します。
  3. values[-steps:] は前に移る末尾で [4, 5] です。
  4. values[:-steps] は残りの [1, 2, 3] で、+ が2つをつなぎます。

どんな場面で使う?

  • 順番に回る当番やスケジュール。
  • 循環バッファーやずれていくデータの窓。
  • スライスと剰余に関する面接問題。

使わなくてよいとき

  • 1ステップずつ何度も回転する場合:collections.deque.rotate がその場で効率よく行います。
  • 余分なメモリが問題になる巨大なリスト:その場で反転する方法ならコピーを避けられます。

動きで理解する

箱をクリックするかスライダーでインデックスを選びます。挿入や削除をすると、後ろの要素がすべてずれる理由がわかります。

サンプルコード

コードを実行 →
main.py
def rotate_right(values, steps):
    if not values:
        return []
    steps %= len(values)
    return values[-steps:] + values[:-steps]

print(rotate_right([1, 2, 3, 4, 5], 2))
この例の実行ボタンを作成

実行結果

[4, 5, 1, 2, 3]

コードの解説

steps %= len(values)という余りの計算は、回転数がリストの長さより大きい場合に対応するためのものです。5個の要素のリストを7回回転させるのは、2回回転させるのと同じだからです。スライスvalues[-steps:]とvalues[:-steps]で末尾のk個と残りを取り出し、新しい順番でつなげます。時間とメモリの計算量はどちらもO(n)です。

値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。

発展問題

下のヒントにしたがってコードを書き換えてみましょう。自分で変えて結果を確かめると、コードを読むだけよりずっと深く理解できます。

  1. 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
  2. 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
  3. 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
Pythonコンパイラで実行 →

よくある間違い

回転数0を忘れる

values[-0:] はリスト全体なので、% がないと結果が2倍になります。

問題
return values[-steps:] + values[:-steps]  # steps = 5 gives a list of 10
修正
steps %= len(values)
return values[-steps:] + values[:-steps]

このレッスンを終えましたか?

学習済みにすると進み具合を記録できます。

チャレンジで練習する

このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。

すべてのチャレンジ