IndexError: list index out of range

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

リストのお尻に0を移動させる問題

問題

今日はMove all zeroes to end of arrayの問題にチャレンジする。この問題は、ランダムな値をもつリストの要素の順番を並び替える問題で、0以外を前に移動させ、0は後ろに移動させる問題。

Input : [1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9]
Output: [1, 9, 8, 4, 2, 7, 6, 9, 0, 0, 0, 0]

実装

問題を2つに分けて考えるとわかりやすいとのこと。つまり、「0以外の要素を前に移動させる部分」と「0で埋める部分」の2つ。まずは「0以外の要素を前に移動させる部分」については、インデックスiとcountを使ってiでリストをループさせて値を確認し、インデックスcountで値を移動させる場所を決める。この部分がおわると、countのインデックス以降は、「0で埋める部分」となるので、そこに0を入れていけば、問題を解決できる。 f:id:AZUMINO:20210223134743j:plain


from typing import List


def pushZerosToEnd(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    count = 0

    for i in range(len_numbers):
        if numbers[i] != 0:
            numbers[count] = numbers[i]
            count += 1

    while count < len_numbers:
        numbers[count] = 0
        count += 1

if __name__ == '__main__':
    numbers = [1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9]
    print(numbers)
    pushZerosToEnd(numbers)
    print(numbers)

[1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9]
[1, 9, 8, 4, 2, 7, 6, 9, 0, 0, 0, 0]

もっと短く書くこともできる。


from typing import List


def pushZerosToEnd2(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    count = 0

    for i in range(0, len_numbers):
        if (numbers[i] != 0):
            numbers[count], numbers[i] = numbers[i], numbers[count]
            count += 1

if __name__ == '__main__':
    numbers = [1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9]
    print(numbers)
    pushZerosToEnd2(numbers)
    print(numbers)

[1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9]
[1, 9, 8, 4, 2, 7, 6, 9, 0, 0, 0, 0]

正負の値を含むリストの要素を正負交互に並び替える

問題

今日はRearrange positive and negative numbers in O(n) time and O(1) extra spaceの問題にチャレンジする。

この問題は、正の数と負の数の両方がランダムな順序で含まれていて、正の数と負の数が交互に配置されるように要素を並び替える問題。正の数と負の数は同じではなく、より多くの正の数がある場合、それらはリストの最後に表示しておけば良い。さらに負の数がある場合は、それらも最後に表示しておく。

Input : [-1, 2, -3, 4, 5, -7, 8, 9]
Output: [4, -3,  5,-1, 2, -7, 8, 9]

実装

問題を対処するためには、QuickSortのパーティションの考え方を利用するのが良いとのこと。つまり、ランダムなリストを一度、正の数と負の数にパーティションを利用して分離。すべての負の数が正の数の前に配置できたら、負の数と正の数が交互に並び替えるように、値をスワップしていく。

いつもどおり、デバッグの要素を図解してイメージしやすいようにする。ランダムなリストを一度、正の数と負の数にパーティションを利用して分離する部分がこの画像のイメージ。

f:id:AZUMINO:20210219003350j:plain

すべての負の数が正の数の前に配置できたら、負の数と正の数が交互に並び替えるように、値をスワップしていく部分がこの画像のイメージ。 f:id:AZUMINO:20210219003401j:plain


from typing import List

def ReArrange(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)

    i = -1
    for j in range(len_numbers):
        if numbers[j] < 0:
            i += 1
            numbers[i], numbers[j] = numbers[j], numbers[i]

    pos, neg = i + 1, 0

    while pos < len_numbers and neg < pos and numbers[neg] < 0:
        numbers[neg], numbers[pos] = numbers[pos], numbers[neg]
        pos += 1
        neg += 2


if __name__ == '__main__':
    numbers = [-1, 2, -3, 4, 5, -7, 8, 9]
    print(numbers)
    ReArrange(numbers)
    print(numbers)

[-1, 2, -3, 4, 5, -7, 8, 9]
[4, -3, 5, -1, 2, -7, 8, 9]

リストの要素をリバースする問題

問題

今日はWrite a program to reverse an array or stringの問題にチャレンジする。この問題は、リストの要素をリバースする問題。

Input : [1, 2, 3]
Output: [3, 2, 1]

Input : [4, 5, 1, 2]
Output: [2, 1, 5, 4]

実装

基本的な方針は、start, endの2つのインデックスを用意し、startは左から右に、endは右から左にインデックスを操作し、挟み撃ちしながら、各位置の要素をスワップしていけば、リバースすることができる。インデックスが交わる部分は、リストが[4, 5, 1, 2]のように偶数であれば、[start=0, end=3]→swap→[start=1, end=2]→swap→[start=2, end=1]→falseとなり、不要な要素の入れ替えが発生しない。一方でリストが[1, 2, 3, 4, 5]のように奇数の場合は、[start=0, end=4]→swap→[start=1, end=3]→swap→[start=2, end=2]→falseとなり、真ん中の要素の入れ替えが発生しない。



from typing import List

def swap(numbers: List[int]) -> List[int]:
    start = 0
    end = len(numbers) - 1

    while start < end:
        numbers[start], numbers[end] = numbers[end], numbers[start]
        start += 1
        end -= 1

if __name__ == '__main__':
    numbers = [4, 5, 1, 2]
    print(numbers)
    swap(numbers)
    print(numbers)

    numbers = [1, 2, 3]
    print(numbers)
    swap(numbers)
    print(numbers)

    numbers = [1,2,3,4,5,6,7,8,9]
    print(numbers)
    swap(numbers)
    print(numbers)

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

実装

このような繰り返すような処理は再帰を使っても書き直せる。



from typing import List

def swap2(numbers: List[int], start: int, end: int) -> List[int]:
    if start >= end:
        return
    numbers[start], numbers[end] = numbers[end], numbers[start]
    swap2(numbers, start+1, end-1)

if __name__ == '__main__':
    numbers = [4, 5, 1, 2]
    print(numbers)
    swap2(numbers, 0, len(numbers) - 1)
    print(numbers)

    numbers = [1, 2, 3]
    print(numbers)
    swap2(numbers, 0, len(numbers) - 1)
    print(numbers)

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

リストの要素を再配置する問題

問題

今日はRearrange an array such that arr[i] = iの問題にチャレンジする。この問題は、0からn–1の範囲の長さnの要素のリストがあり、List[i]=iとなるように配列を再配置する。すべての要素が配列に存在するとは限らないので、要素が存在しない場合、配列には-1を表示する。

0から9の範囲の長さ10の要素のリストがあれば、本来であればoriginのようなリストになるが、inputには、0,5,7,8の要素がないので、その場所については-1を表示する。

# Input : [-1, -1, 6, 1, 9, 3, 2, -1, 4, -1]
# Output: [-1, 1, 2, 3, 4, -1, 6, -1, -1, 9]
# Origin: [ 0, 1, 2, 3, 4,  5, 6,  7,  8, 9]

実装

まずは簡単な実装の内容でチャレンジする。インデックスを2つ使用し、iで「リストの位置」を決めて、そこに「入るべきリストの要素」をインデックスjで見つけてくるという方法。見つかれなければ、-1を変わりに代入しておく。

f:id:AZUMINO:20210212210035j:plain


from typing import List

def Rearrange(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)

    for i in range(len_numbers):
        for j in range(len_numbers):
            if numbers[j] == i:
                numbers[j], numbers[i] = numbers[i], numbers[j]

    for i in range(len_numbers):
        if numbers[i] != i:
            numbers[i] = -1

if __name__ == '__main__':
    numbers = [-1, -1, 6, 1, 9, 3, 2, -1, 4, -1]
    print(numbers)
    Rearrange(numbers)
    print(numbers)


[-1, -1, 6, 1, 9, 3, 2, -1, 4, -1]
[-1, 1, 2, 3, 4, -1, 6, -1, -1, 9]

実装2

集合を使う方法。まずはリストの要素を集合の中に保存しておいて、そこからiで「リストの位置」を管理しつつ、集合の中にインデックスと一致する値があるかを検索。集合のなかにあるのであれば、その値をリストの適切な位置に入れていく、という方法。


from typing import List

def Rearrange2(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    cache = set()

    # for i in range(len(A)):
    #     s.add(A[i])
    cache = {numbers[i] for i in range(len_numbers)}

    for i in range(len_numbers):
        if i in cache:
            numbers[i] = i
        else:
            numbers[i] = -1
    return numbers

if __name__ == '__main__':
    numbers = [-1, -1, 6, 1, 9, 3, 2, -1, 4, -1]
    print(numbers)
    Rearrange2(numbers)
    print(numbers)

[-1, -1, 6, 1, 9, 3, 2, -1, 4, -1]
[-1, 1, 2, 3, 4, -1, 6, -1, -1, 9]

リストを分割し、最初の部分を最後にくっつける

問題

今日はSplit the arrays and add the first part to the endの問題にチャレンジ。これは、指定されたkのインデックスの位置でリストを分割し、それらをスワップして、最初の部分をリストのお尻に持ってくるという問題。

Input: [12, 10, 5, 6, 52, 36]
k = 2
Output: [5, 6, 52, 36, 12, 10]

kが2なので、リストを[12, 10]と[5, 6, 52, 36]に分割し、最初の部分を最後にくっつけることで、このような[5, 6, 52, 36,12, 10]というリストを作成するという問題。

実装

お題がリストを「スプリット」してうんたらとあるが、下記の画像のように、スプリットして結合することと、ローテションすることは最終的には同じことができるので、そのように問題を焼き直すとローテション問題と考えることができるので、これまでと同じようにローテションさせる。

f:id:AZUMINO:20210209124643j:plain


from typing import List

def split_list(numbers: List[int], k: int) -> List[int]:
    len_numbers = len(numbers)

    for i in range(0, k):
        tmp = numbers[0]
        for j in range(0, len_numbers - 1):
            numbers[j] = numbers[j + 1]

        numbers[len_numbers - 1] = tmp

    return numbers


if __name__ == '__main__':
    numbers = [12, 10, 5, 6, 52, 36]
    k = 2
    print(split_list(numbers, k))

[5, 6, 52, 36, 12, 10]

ローテションしたリストから指定されたインデックスの要素を検索する

問題

今日はFind element at given index after a number of rotationsにチャレンジする。

この問題はローテションさせる複数の範囲がネストされたリストで渡されるので、その範囲をローテションさせて、指定されたインデックスの要素を検索する問題。下記の例では、まず[0,2]の範囲でローテションさせて、そのローテションされたリストをさらに[0,3]の範囲でローテションさせる。そして、指定されたインデックスは1なので、その要素を出力する、という問題。

imput: [1,2,3,4,5]
range: [[0,2],[0,3]]
index: 1
output: 3

range: [0,2] → Right Rotation → [3,1,2,4,5]
range: [0,3] → Right Rotation → [4,3,1,2,5]
index 1 is 3

実装

指定されたすべての範囲でリストを実際にローテションさせ、最終的に変更されたリストの指定されたインデックスで要素を返す愚直な方法しか思いつかなかった。そして、この実装には問題もあって、リストが指定されたすべての範囲より小さいときに、インデックスエラーになるので、入力されたリストと、指定されたローテション範囲を比較して、内容に応じた処理を記述する必要がある。


from typing import List


def findElement(numbers: List[int], ranges: List[List[int]], index: int):
    len_list = len(ranges)

    for i in range(len_list):

        len_numbers = len(numbers[ranges[i][0]:(ranges[i][1] + 1)])
        temp = numbers[len_numbers-1]

        for j in range(len_numbers - 1, 0, -1):
            numbers[j] = numbers[j - 1]

        numbers[0] = temp
        # display for check
        print(numbers)

    return numbers[index]


if __name__ == '__main__':
    numbers = [1,2,3,4,5]
    ranges = [[0, 2], [0, 3]]
    index = 1
    print(findElement(numbers, ranges, index))

3

dequeを使ったリストのローテション

問題

今日はPrint left rotation of array in O(n) time and O(1) spaceの問題に挑戦する。今までチャレンジしてきたローテション問題をdequeを使って解く方法でチャレンジする。

k = 3
Input: [1, 3, 5, 7, 9]
output: [7, 9, 1, 3, 5]

まずは基本的なローテションを実装してから、デックを使ったローテションの実装にチャレンジする。

実装1


from typing import List

def leftRotate(numbers: List[int], k: int):
    len_numbers = len(numbers)
    mod = k % len_numbers
    res =[]

    for i in range(len_numbers):
        res.append(numbers[(mod + i) % len_numbers])
    return res


if __name__ == '__main__':
    numbers = [1, 3, 5, 7, 9]
    print(leftRotate(numbers, k=3))

[7, 9, 1, 3, 5]

dequeについて

Pythonの標準ライブラリcollectionsモジュールのdeque型は、リストに比べて、先頭の要素に対する削除や追加、挿入が速い。一方で、両端以外の要素へのアクセスは遅いデメリットもある。


import collections

d = collections.deque()

for i in range(5):
    d.append(i)

print(d)
d.rotate(-3)
print(d)

for _ in range(5):
    print(d.pop(), end=' ')

deque([0, 1, 2, 3, 4])
deque([3, 4, 0, 1, 2])

rotate()メソッドでローテションさせることができるので、これを使って回転させたものを左から取り出す。


import collections

d = collections.deque()
for i in range(5):
    d.append(i)
    
d.rotate(-3)

for _ in range(5):
    print(d.popleft(), end=' ')

3 4 0 1 2 

実装2

ということでdequeについては少し理解ができたので、この問題にチャレンジする。方針としては、リストをdequeに変換し、dequeのメソッドでローテションさせて、リストに戻すという方法。


from collections import deque
from typing import List

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

    numbers.rotate(-k)
    numbers = list(numbers)

    res = []

    for i in range(len_numbers):
        res.append(numbers[i])

    return res


if __name__ == '__main__':
    numbers = [1, 3, 5, 7, 9]
    print(leftRotate(numbers, k=3))

[7, 9, 1, 3, 5]