Pythonで学ぶ配列回転の反転アルゴリズム：効率的な左回転の実装方法

はじめに

Pythonでは、回転した配列を反転（リバース）する処理が必要になることがあります。本記事では、反転アルゴリズム（Reversal Algorithm）を使って配列を左回転する方法を解説します。この手法では、リストを走査して要素を入れ替えるメソッド、リストを回転させるメソッド、そして結果を表示するメソッドの3つを定義し、シンプルなループとインデックス操作だけで実装できます。

反転アルゴリズムの仕組み

反転アルゴリズムによる左回転は、次の3つのステップで構成されます。

• まず、先頭から「d − 1」番目までの部分を反転する
• 次に、「d」番目から末尾までの部分を反転する
• 最後に、配列全体を反転する

この3段階の反転により、追加の配列を作ることなく、配列全体を左方向へd要素分だけ回転させることができます。

サンプルコード

def reverse_list(my_list, begin, end):
    while (begin < end):
        temp = my_list[begin]
        my_list[begin] = my_list[end]
        my_list[end] = temp
        begin += 1
        end = end-1
def left_rotate(my_list, to_rotate):
    n = len(my_list)
    reverse_list(my_list, 0, to_rotate-1)
    reverse_list(my_list, to_rotate, n-1)
    reverse_list(my_list, 0, n-1)
def print_it(my_list):
    for i in range(0, len(my_list)):
        print(my_list[i])
my_list = [34, 42, 56, 78, 9, 0, 23]
print("The list is :")
print(my_list)
print("The left_rotate method is being called")
left_rotate(my_list, 3)
print("The list after rotation is : ")
print_it(my_list)

実行結果

The list is :
[34, 42, 56, 78, 9, 0, 23]
The left_rotate method is being called
The list after rotation is :
78
9
0
23
34
42
56

コードの解説

• reverse_list：指定された範囲（begin〜end）の要素を両端から順にスワップしていくことで、リストの一部を反転するメソッドです。
• left_rotate：上記の3ステップを実行し、ピボットとなる位置の値に基づいてリストを左回転させるメソッドです。
• print_it：リストの各要素を1行ずつコンソールに出力するメソッドです。
• サンプルとして7つの整数を含むリストを定義し、最初にその内容をコンソールに表示します。
• left_rotateメソッドを呼び出して3要素分の左回転を行い、回転・反転後の要素をコンソールに表示します。

まとめ

反転アルゴリズムは、追加の配列を必要とせず、時間計算量O(n)・空間計算量O(1)で配列を回転できる効率的な手法です。実装もシンプルなため、技術面接や競技プログラミングでも頻繁に活用されます。ぜひ自分のコードにも取り入れてみてください。