リストのローテーションにおけるブロックスワップアルゴリズム

問題

今回もリストのローテーションを勉強する。問題はgeeksforgeeksのBlock swap algorithm for array rotationにあるローテーション問題。アルゴリズムの中身は下記のような内容を実装できれば良い。

1. A = arr [0..d-1]およびB = arr [d..n-1]を初期化し、AのサイズがBのサイズと等しくなるまで次の手順を実行します
    → a Aが短い場合は、BrがAと同じ長さになるようにBをBlとBrに分割します。AとBrを交換して、ABlBrをBrBlAに変更します。 これでAが最終位置にあるので、Bの断片を繰り返します。
    → b Aが長い場合は、AlがBと同じ長さになるようにAをAlとArに分割し、AlとBを交換してAlArBをBArAlに変更します。 これでBが最終位置にあるので、Aの断片を繰り返します。
2. 最後に、AとBのサイズが等しい場合は、それらをブロックスワップします。

実装

d=4で図解するとこんな感じになる。AとBにわけて、長い方を短い方とサイズを揃えてスワップ。そして、この時点でBの並び替えは完了している。Aは1,2,3,4にしたいが、4,1,2,3になっているので、この状態から1,2,3,4にするには、左端のインデックスを固定して右端からインデックスをずらしながらスワップしていくと、1,2,3,4になるので、並び替えたい5,6,7,1,2,3,4になる。

from typing import List

def leftRotate(numbers: List[int], d: int):
    len_numbers = len(numbers)

    if d == 0 or d == len_numbers:
        return

    i = d
    j = len_numbers - d
    while i != j:
        # A is shorter
        if i < j:
            swap(numbers, d - i, d + j - i, i)
            j -= i
        # B is shorter
        else:
            swap(numbers, d - i, d, j)
            i -= j

    swap(numbers, d - i, d, i)


def swap(numbers: List[int], fi: int, si: int, d: int):
    for i in range(d):
        numbers[fi + i], numbers[si + i] = numbers[si + i], numbers[fi + i]


if __name__ == '__main__':
    numbers = [1, 2, 3, 4, 5, 6, 7]
    leftRotate(numbers, 4)
    print(numbers)

[5, 6, 7, 1, 2, 3, 4]

swap()は特定の開始位置と終了位置をインデックスで指定し、d回ずらしながらスワップする。そのため、最初のスワップでは3回ずれながらスワップするが、Bの部分を並び直したあとは、Aの部分を1回ずつスワップしている。

再帰を使うパターンもあったけど、それはまた今度。