問題
今回はReversal algorithm for array rotationにあるリストの並びをローテーションないしスワップさせて、リストのブロック要素を反転する方法を勉強する。具体的には下記のようなリストがあったときに、dで指定した数値分リストを分割し、その分割したブロック内で要素をスワップし、ブロックを反転させることが目的。
実装
まずは問題を分割できそうなのか考えていく。画像のように書き下していくと、まずリストを分割してブロックを作る、片方のブロックをスワップする、もう片方のブロックをスワップする、最後にリストを全部スワップする、という感じ。挟み撃ち系のインデックスの動かし方についてのイメージは、iとjがあったとすると、片方はインクリメントして、もう片方はデクリメントしていけばうまくインデックスを動かせそう。
まずは、リストをスワップするreverse()を作成する。
from typing import List
def reverse(numbers: List[int], i: int, j: int):
while i < j:
numbers[i] , numbers[j] = numbers[j] , numbers[i]
i += 1
j -= 1
if __name__ == '__main__':
l = [1, 2, 3, 4, 5, 6, 7]
reverse(l, 0, len(l)-1)
print(l)
[7, 6, 5, 4, 3, 2, 1]
インデックスの部分の挟み撃ちを可視化しておく。例えば21個の要素があった場合、i=0とj=20から始まり、最終的にi=10とj=10となって、while文の条件から外れることになる。
from typing import List
def reverse(numbers: List[int], i: int, j: int):
while i < j:
numbers[i] , numbers[j] = numbers[j] , numbers[i]
print('i={}'.format(i), end=' ')
print('j={}'.format(j), end=' ')
print()
i += 1
j -= 1
if __name__ == '__main__':
l = [i for i in range(21)]
reverse(l, 0, len(l)-1)
i=0 j=20
i=1 j=19
i=2 j=18
i=3 j=17
i=4 j=16
i=5 j=15
i=6 j=14
i=7 j=13
i=8 j=12
i=9 j=11
最終的にはこのようになる。最初の画像のようにAをリバースして、Bをリバースして、全部リバースする部分は、reverse()の開始終了位置をうまく設定することで、思い通りに動いてくれる。
from typing import List
def reverse(numbers: List[int], i: int, j: int):
while i < j:
numbers[i] , numbers[j] = numbers[j] , numbers[i]
i += 1
j -= 1
def Rotation(numbers: List[int], d: int):
if d == 0:
return numbers
len_numbers = len(numbers)
d = d % len_numbers
reverse(numbers, 0, d - 1)
reverse(numbers, d, len_numbers - 1)
reverse(numbers, 0, len_numbers - 1)
if __name__ == '__main__':
l = [1, 2, 3, 4, 5, 6, 7]
Rotation(l, d=2)
print(l)
[3, 4, 5, 6, 7, 1, 2]
途中ででてきたd = d % len_numbersの部分は、リストを分割する位置がリストの長さよりも大きい場合に循環させて戻るようにする処理。
nums = [i for i in range(1, 22, 1)]
for num in nums:
print(('i={}'.format(num), num % 7), end=' ')
if num % 7 == 0:
print()
print('-'*10)
('i=1', 1) ('i=2', 2) ('i=3', 3) ('i=4', 4) ('i=5', 5) ('i=6', 6) ('i=7', 0)
----------
('i=8', 1) ('i=9', 2) ('i=10', 3) ('i=11', 4) ('i=12', 5) ('i=13', 6) ('i=14', 0)
----------
('i=15', 1) ('i=16', 2) ('i=17', 3) ('i=18', 4) ('i=19', 5) ('i=20', 6) ('i=21', 0)
----------
