drkcore

2010/01/12 10:47:48

pythonでpermutation

Project Eulerを解いていくには篩とか素因数分解とか組み合わせ発生用の関数を良く使う。

permutation用のジェネレータを見つけた。

def permutations(L):
    if len(L) == 1:
        yield [L[0]]
    elif len(L) >= 2:
        (a, b) = (L[0:1], L[1:])
        for p in permutations(b):
            for i in range(len(p)+1):
                yield p[:i] + a + p[i:]

再帰の中でyieldが使われている場合の動きのイメージがまだピンとこないなぁ。

それから、インデックスの範囲外は空リストが返ってくるからlispとかhaskellっぽく書けるのか。

>>> a = [1,2,3,4]
>>> a[1:]
[2, 3, 4]
>>> a[2:]
[3, 4]
>>> a[3:]
[4]
>>> a[4:]
[]
>>> a[5:]
[]
>>> a[:0]
[]

Comments