いももちのきもち

新米プログラマによる技術的メモ

配列を逆順に並べ替える

配列を逆順にする方法を考えます(pythonなのでリストを使います)。

言語組み込みのメソッド

最初に言語組み込みのメソッドを使ってみます。

ls = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
ls.reverse()
print ls
ls = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
print ls[::-1]
ls = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
rls = []
for i in reversed(ls):
    rls.append(i)
print rls

言語組み込みのメソッドを使わず逆順にする

  • example 1
# coding: utf-8
ls = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
rls = []
for i in xrange(n):
    rls.append(n - i - 1)
print rls

元のリストを残してあります。メモリ領域が古いリストと新しいリスト両方必要になります。防御的すぎるかもしれません。

  • example 2
# coding: utf-8
# in placeで逆順にする。両端から中央に向かって要素を交換していく。
ls = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
for i in xrange(n):
    if i >= n - i - 1:
        break
    ls[i], ls[n - i -1] = ls[n - i- 1], ls[i]
print ls


最近Scalaをかじっているので、最後に再帰関数版をどうぞ

  • example 3
# coding: utf-8
# リストを先頭要素(head)とその他(tail)にわけ、head要素をtail要素群の後ろに連結、以下tail群に対して同じ操作を繰り返す
ls = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]

def head(ls):
    return [ls[0]]
    
def tail(ls):
    return ls[1:]

def rev(ls):
    if not ls:
        return ls
    else:
        #print tail(ls), head(ls) 
        return rev(tail(ls)) + head(ls) # 再帰

print rev(ls)
# rev関数内のprint文;  tail(ls), head(ls)
[1, 4, 1, 5, 9, 2, 6, 5, 3][3] 
[4, 1, 5, 9, 2, 6, 5, 3][1] 
[1, 5, 9, 2, 6, 5, 3][4] 
[5, 9, 2, 6, 5, 3][1] 
[9, 2, 6, 5, 3][5] 
[2, 6, 5, 3][9]
[6, 5, 3][2] 
[5, 3][6] 
[3][5] 
[][3] 

# 結果
[3, 5, 6, 2, 9, 5, 1, 4, 1, 3]

# ref. Scalaスケーラブルプログラミング第2版P.298