問題
今回はProgram for array rotationにあるリストの並びをローテーションする方法を勉強する。具体的には下記のようなリストがあったときに、dで指定した数値分、リストを左にローテーションすることが目的。
d=2 pre: [1, 2, 3, 4, 5, 6, 7] ↓ post:[3, 4, 5, 6, 7, 1, 2]
実装1(NG)
1つ目の方法としてはtmpにいったん値を逃して、その逃した値をお尻に持ってくるというもの。画像のようなイメージ。
さきほどの画像のイメージで実装してみる。リストをスライスで分割し、ローテーションさせて、戻すという方法だと、リストの長さよりもローテーションの回数が多くなるとうなく動かない。
from typing import List
def leftRotate(numbers: List[int], d: int):
tmp = numbers[:d]
rest = numbers[d:]
rest.extend(tmp)
return rest
if __name__ == '__main__':
l = [1, 2, 3, 4, 5, 6, 7]
print(leftRotate(l, d=2))
l = [1, 2, 3, 4, 5, 6, 7]
print(leftRotate(l, d=10))
# d=2
[3, 4, 5, 6, 7, 1, 2]
# d=10
[1, 2, 3, 4, 5, 6, 7]
原因は下記の通り。最初の分割でリストの要素がすべて対象になり、結局をこれをリターンするので、何も起こってないようにみえる。
print(l[:10])
[1, 2, 3, 4, 5, 6, 7]
print(l[10:])
[]
実装2
さきほどのようにするのであれば、入力してきた値をインデックスの範囲に収まるように変換し直すみたいな処理が必要かと思う。なので、ここではループを使って、要素を1つづつずらす関数LeftRotationを作り、その関数をd回繰り返す関数を作成する。
from typing import List
def LeftRotation(numbers: List[int]):
len_numbers = len(numbers)
temp = numbers[0]
for i in range(len_numbers - 1):
numbers[i] = numbers[i + 1]
numbers[len_numbers - 1] = temp
if __name__ == '__main__':
l = [1, 2, 3, 4, 5, 6, 7]
LeftRotation(l)
print(l)
# 1要素ずれている
[2, 3, 4, 5, 6, 7, 1]
ずれていくイメージは下記の通り。
[1, 2, 3, 4, 5, 6, 7]
---------- for-loop
[2, 2, 3, 4, 5, 6, 7] # i = 0
[2, 3, 3, 4, 5, 6, 7] # i = 1
[2, 3, 4, 4, 5, 6, 7] # i = 2
[2, 3, 4, 5, 5, 6, 7] # i = 3
[2, 3, 4, 5, 6, 6, 7] # i = 4
[2, 3, 4, 5, 6, 7, 7] # i = 5
----------
[2, 3, 4, 5, 6, 7, 1]
ということで、LeftRotation()を使って、Rotation()を作る。いきなり、何個ずらすと考えるのではなく、1個ずらす、そして、それを繰り返すと問題を分割して考えることが大切なんだろう。私のようなワナビーには特に。
from typing import List
def LeftRotation(numbers: List[int]):
len_numbers = len(numbers)
temp = numbers[0]
for i in range(len_numbers - 1):
numbers[i] = numbers[i + 1]
numbers[len_numbers - 1] = temp
def Rotation(numbers: List[int], d: int):
for i in range(d):
LeftRotation(numbers)
if __name__ == '__main__':
l = [1, 2, 3, 4, 5, 6, 7]
Rotation(l, 2)
print(l)
# [3, 4, 5, 6, 7, 1, 2]
実装3
さきほどは左ローテーションだったが、右ローテーションの場合はどうすればよいか。イメージとしてはさきほどの逆でやればいけそう。numbers[-1]でリストの最後の要素が取れるので、あとは数字の大きい方から小さい方にインデックスをすすめたいので、range(len_numbers - 1, 0, -1)とすることで、インデックスを6, 5, 4, 3, 2, 1と動かせる。最後のインデックスが1で良いのは、numbers[i] = numbers[i - 1]はnumbers[1] = numbers[0]となるので、この時点で終了してOKなので。
from typing import List
def RightRotation(numbers: List[int]):
len_numbers = len(numbers)
temp = numbers[-1]
for i in range(len_numbers - 1, 0, -1):
numbers[i] = numbers[i - 1]
numbers[0] = temp
def Rotation(numbers: List[int], d: int):
for i in range(d):
RightRotation(numbers)
if __name__ == '__main__':
l = [1, 2, 3, 4, 5, 6, 7]
Rotation(l, 2)
print(l)
[6, 7, 1, 2, 3, 4, 5]
