2 つの正の整数 m と n があるとき、その最大公約数(m と n のどちらでも割り切れるような数のうち最も大きな数)を計算するアルゴリズム。
def euclid(m, n):
while True:
r = m % n
if r == 0:
return n
m, n = n, r> euclid(119, 544) 17 > euclid(544, 119) # ひっくり返しても OK 17
たとえば、リスト [1, 2, 3, 4, 5] の中の偶数のみのリストは、
>>> newlst = []
>>> for i in [1, 2, 3, 4, 5]:
if i % 2 == 0:
newlst.append(i)
>>> newlst
[2, 4]
と書けますが、これをリスト内包表記を用いると次のように書くことが出来ます:
>>> [x for x in [1, 2, 3, 4, 5] if x % 2 == 0] [2, 4]
リストの中で値が 10 より大きいだけからなるリストは:
>>> lst = [3, 12, 4, -90, 13, 33] >>> [x for x in lst if x > 10] [12, 13, 33]
リストのそれぞれの要素を 2 倍したリストは:
>>> lst = [1, 2, 3, 4, 5] >>> [x * 2 for x in lst] [2, 4, 6, 8, 10]
となります。
リスト内包表記を使うといろいろな面白い関数が書けます。たとえば、Python では組み込み関数に filter があります。
>>> help('filter')
Help on built-in function filter:
filter(...)
filter(function or None, sequence) -> list, tuple, or string
Return those items of sequence for which function(item) is true. If
function is None, return the items that are true. If sequence is a tuple
or string, return the same type, else return a list.
filter は sequence のうち function が真を返すもののみのリストを返してくれます。たとえば、偶数のみのリストが欲しいときには:
>>> def even(n): # n が偶数なら真(True)を返す
return n % 2 == 0
>>> filter(even, [2, 44, 3, 87, 90, 34, 33]
[2, 44, 90, 34]
この filter と似たような動作をするものはリスト内包表記を使って次のように書けます。
def filter2(f, lst): return [x for x in lst if f(x)]
>>> filter2(even, [2, 44, 2, 87, 90, 34, 33]) [2, 44, 90, 34]
filter と似たような性質を持つ組み込み関数には、ほかに map があります。map はリストの要素それぞれに対し、ある関数を適用した値からなるリストを返します。
>>> def add10(n):
return n + 10
>>> map(add10, [1, 2, 3, 4, 5])
[11, 12, 13, 14, 15]
この map 関数に似た関数はリスト内包表記を使って次のように書けます。
def map2(f, lst): return [f(x) for x in lst]
>>> map2(add10, [1, 2, 3, 4, 5]) [11, 12, 13, 14, 15]
リスト内包表記を用いたクイックソートをみてみましょう。
def qsort(lst):
if len(lst) == 0:
return lst
else:
x, xs = lst[0], lst[1:]
return qsort([a for a in xs if a < x]) + [x] + qsort([a for a in xs if a >= x])>>> qsort([8, 44, 2, -3, 76, 100]) [-3, 2, 8, 44, 76, 100]
リストに対する + 演算子はリストの連結になります。
>>> [1, 2, 3] + [4, 5, 6] [1, 2, 3, 4, 5, 6] >>> [1, 2, 3] + [3] + [9, 10] [1, 2, 3, 3, 9, 10]
また lst[1:] はスライスといって、リストの一部を取り出す操作です。リストをスライスした結果はリストです。
>>> lst = [1, 2, 3, 4, 5] >>> lst[1:] # 1 番目以降のリスト [2, 3, 4, 5] >>> lst[2:4] # 2 番目から 4 番目の前までのリスト [3, 4] >>> lst[:3] # 3 番目の前までのリスト [1, 2, 3]
qsort 関数の中身を見ていきます。
def qsort(lst):
if len(lst) == 0:
return lst
else:
x, xs = lst[0], lst[1:]
return qsort([a for a in xs if a < x]) + [x] + qsort([a for a in xs if a >= x])
qsort が受け取ったリストが空なら、それを返します。受け取ったリストが空でないときは、リストの先頭の要素と比べて、値の大きいグループと小さいグループに分けます。たとえば、
[8, 44, 2, -3, 76, 100]
というリストであれば、リストの先頭の値、つまり 8 に対して、それよりも小さいものとそれ以上のものとに分けます：
+---+---+---+---+---+---+ | 8| 44| 2| -3| 76|100| +---+---+---+---+---+---+
↓ 8 に対してそれよりも小さなグループとそれ以上のグループに分ける
+---+---+ +---+---+---+
| 2| -3| < 8 <= | 44| 76|100|
+---+---+ +---+---+---+
この分割を行っているのが
[a for a in xs if a < x]
と
[a for a in xs if a >= x]
です。8 に対してそれよりも小さなグループと、それ以上のグループのリストを作り、さらにそのリストを qsort の引数としています。なので、
+---+---+ | 2| -3| +---+---+
↓
+---+
| -3| < 2 <= なし(空のリスト)
+---+
もう片方のリストは、
+---+---+---+ | 44| 76|100| +---+---+---+
↓
+---+ +---+ | 76| < 44 <= |100| +---+ +---+
という風にグループ分けされます。そしてさらに同じように分けられたリストに対して再び qsort を呼び出します。
[76]
を受け取った qsort は、このリストに対して
+---+ | 76| +---+
↓
なし(空のリスト) < 76 <= なし(空のリスト)
という分割を行います。
再帰関数は、自分の中で再び自分自身を呼び出しますが、常に自分自身を呼び出しているわけではありません(もしそうなら、処理が終わることがありません)。再帰関数 qsort が自分自身を呼んでいないのは、受け取った引数が空の場合です。もし受け取った引数が空のリストなら、それをそのまま返しています。
さて、ここからは qsort からの戻り値がどのように処理されるかを見ていきます。
qsort([a for a in xs if a < x]) + [x] + qsort([a for a in xs if a >= x])
qsort から返されたリストを連結しています。どのように連結しているのかというと、x より小さいグループのリストの後ろに、そのグループよりも大きな値の x のリスト(要素は x のみ)を連結し、そして x かそれよりも大きな値をもつグループのリストを連結しています。これはつまりソートしている、ということになります。
[8, 44, 2, -3, 76, 100]
というリストがどのように分割され、そして連結されるのかを通しで見てみましょう。
1. [8, 44, 2, -3, 76, 100]
↓ 8 未満と 8 以上に分ける(以下同様な方法で分割していく)
2. [2, -3] [8] [44, 76, 100]
3. [-3] [2] [] [] [44] [76, 100]
4. [] [-3] [] [] [76] [100]
--- 分割終了 ---
--- 返されたリストを連結させる ---
4. [-3] [76, 100]
3. [-3, 2] [44, 76, 100]
2. [-3, 2, 8, 44, 76, 100]
1. --- ソート完了 ---
なお、リストに対して空のリストを連結しても何も変化はありません。
>>> [1, 2, 3] + [] [1, 2, 3]
qsort 関数はリスト内包表記を使って書きましたが、これは filter 関数を使っても同じように出来ます。
今度はリスト内包表記を使って最大公約数を求めてみましょう。
ある正の整数の約数からなるリストを返す関数 divr は次のように作ります。
def divr(n): return [x for x in range(1, n+1) if n % x == 0]
>>> div(64) [1, 2, 4, 8, 16, 32, 64]
この divr を使って、2 つの正の整数の最大公約数を求める関数を作ります。
def gcd(m, n): return [x for x in divr(m) if n % x == 0][-1]
>>> gcd(544, 119) 17
リストの添え字を負にした場合は、リストの末尾からのインデックス指定となります。-1 がリストのおしりの要素で、-2 がその一つ前の要素となります。
>>> [1, 2, 3][-1] 3 >>> [1, 2, 3][-2] 2
また div は素数を求めるのにも使えます。
def prime(n): return len(divr(n)) == 2
>>> filter(prime, range(2, 30)) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
以下の qsort 関数をリスト内包表記を使わずに filter 関数を用いて書き直してください(解答)。
def qsort(lst):
if len(lst) == 0:
return lst
else:
x, xs = lst[0], lst[1:]
return qsort([a for a in xs if a < x]) + [x] + qsort([a for a in xs if a >= x])