IndexError: list index out of range

IndexErrorと仲良しなプログラミング初心者がGeeksForGeeksの問題を Pythonで勉強するためのブログ。計算量には触れてない。有意義な情報ないですよ。

リストのローテーションにおける逆転アルゴリズム

問題

今回はReversal algorithm for array rotationにあるリストの並びをローテーションないしスワップさせて、リストのブロック要素を反転する方法を勉強する。具体的には下記のようなリストがあったときに、dで指定した数値分リストを分割し、その分割したブロック内で要素をスワップし、ブロックを反転させることが目的。

f:id:AZUMINO:20210123044538j:plain

実装

まずは問題を分割できそうなのか考えていく。画像のように書き下していくと、まずリストを分割してブロックを作る、片方のブロックをスワップする、もう片方のブロックをスワップする、最後にリストを全部スワップする、という感じ。挟み撃ち系のインデックスの動かし方についてのイメージは、ijがあったとすると、片方はインクリメントして、もう片方はデクリメントしていけばうまくインデックスを動かせそう。

まずは、リストをスワップする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=0j=20から始まり、最終的にi=10j=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) 
----------