Python で順列を生成

2008年9月29日月曜日

Python で順列を生成

1. 順列の意味

組合せ数学における順列（じゅんれつ、permutation）は、あるひとつの集合から要素を選び出して、順番に意味を持たせて並べる (ordering) ときの、その並び（ordered list, sequence; 有限列）のことである。

うーん、ややこしそう。 (+_+)

数学苦手。どうやって生成するんだろう。

2. アルゴリズム

順列の生成とList内包表記 - 趣味的にっきによると、

与えられたリストから要素を1つ取り出して、残りの要素から再帰的に順列を求めて、それらを結合するアルゴリズムです。 (…)

まずHaskellの場合。 (…)
perms :: Eq a => [a] -> [[a]]
perms [] = [[]]
perms xs = [ h : t | h <- xs, t <- perms (xs \\ [h]) ]

えーーー、こんな簡単なアルゴリズムとは。 (@_@;)

しかし、自分の脳みそではすぐにイメージできない。

Haskell の文法

ゆっくり考えてみよう。

リスト内包表記に書かれていることを、落ちついて眺めてみる。

まず、基本的なこととして (\\) はリストからリストを引く操作。

The \\ function is list difference ((non-associative).

(Data.List より)

リスト内包表記において、リストを生成する元 (生成器) が二つなので、その要素が組み合わされたものが生成される。

cf. 3.11 リスト内包表記

リスト内包表記[ exp | qual₁ , ... , qual_n ]の exp にリストを生成するための (:) が使われている。(:) はリストを生成するためのデータコンストラクタ。

The Haskell 98 Library Report: List Utilities によると、

-- []((:), []), -- This is built-in syntax

これを exp (式)として利用できるのは、式の定義の中で、

gcon (general constructor)

とあるからなのか。

h には、与えられたリストから要素が一つずつ取り出される。 t には、与えられたリストから、その h を取り除いた残りの要素から一つずつ取り出される。これが組み合わされてリストが生成される。

ふぅ (+_+)、やっとこれで、やっていることが理解できた。

しかし、なぜこれで順列を生成することができるのだろうか？

3. 順列における再帰構造

やはり、絵を描いて理解するしかない。

要素が一つの順列、二つの順列、三つの順列…。もうこの辺りで面倒なので、四つの順列は一部のみを描いた。

三つの順列を描いた後に、じっと眺めてから、やっと気がついた。 (@_@) 先ほどのアルゴリズに書かれていたことが、絵に描かれている。

例えば、三つの順列を描いた一番上の要素、1 - 2 – 3 と 1 – 3 – 2 に注目。先頭の「1」を取り除いた部分だけを見ると、「2, 3」の順列と同じ。同じような視点で 1, 2 の順列を見ると、同じく先頭の要素を取り除けば、残りの「要素一つの順列」と見ることができる。「おぉ～、これは (@_@)」と思い、四つの順列も一部を描いたので同じようにして見ると、先頭を取り除いた順列が、残りの要素の順列からなることがわかる。

4. Python で実装

Python ではリスト内包表記が使えるので、 Haskell のコードを真似することができる。

def permutations(L):
    if L == []:
        return [[]]
    else:
        return [[h]+t for i,h in enumerate(L)
                      for t   in permutations(L[:i]+L[i+1:])]

はじめ、リストから要素を一つ取り出し、その要素を取り除いたリストを得る方法がはじめよくわからず。 (+_+) enumerate() を使って対象のリストをインデックスと共に取り出し、そのインデックスを利用して同リストからその要素だけ削除した。

上記のようにリスト内包表記で書く方法がわからなかったときは、次のように書いていた。

def permutations(L):
    if L == []:
        return [[]]
    elif len(L) == 1:
        return [L]
    elif len(L) >= 2:
        result = []
        for i in range(1,len(L)+1):
            result.extend([L[i-1]] + x
                for x in permutations(L[0:i-1]+L[i:]))
        return result

うーん、なんかややこしい。 (+_+)

5. ジェネレータを使った実装

Generator for permutations, combinations, selections of a sequence « ActiveState Code

には、ジェネレータを使った順列、組合せなどが定義されたモジュールがある。

実際に使うときはこれを使うのがよさげ。

6. Haskell のコードを一部修正

ところで、上記 Haskell のコードにおいて、perms [1, 2, 3] と perms [1, 2, 1] の結果を並べて表示させると、

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
[[1,2,1],[1,1,2],[2,1,1],[2,1,1],[1,2,1],[1,1,2]]

あれ？上記二つの結果は、3 を 1 に変更しただけなので、1 と 2 は全て対応していないとおかしい。調べてみたら、The Haskell 98 Library Report: List Utilities によると、

(\\) はリストの差(結合性はない)である。 xs \\ ys の結果は、xs のなかから ys の各要素の最初に出現したものを取り除いた残りである。 (太字は引用者による)

なるほど、(\\) は、最初に出現するものを取り除くから、[1, 2, 1] \\ [1] は 2 回行われるけれど、両方とも先頭の 1 が消されて [2, 1] が返ってしまう。そのために上記のような結果になったようだ。

ということは、Python の enumerate() のような関数を使って、インデックスを用いて要素を削除すればいいわけか。…と思って、Data.List, List operations 辺りをざっと見ても見つけられなかったので、要素から取り出すときに, zip でインデックスに相当するリストとくっつけて取り出し、そこから取り出したインデックスの値で要素指定して削除する関数 takeWithout を定義した。

もっと楽にできる方法ってないのかな？

import Data.List ((\\))

perms    :: Eq a => [a] -> [[a]]
perms [] = [[]]
perms xs = [ h : t | (i,h) <- zip [0..] xs, 
                         t <- perms (takeWithout i xs) ]

takeWithout      :: Int -> [a] -> [a]
takeWithout n xs = take n xs ++ drop (n+1) xs

main = print $ perms [1,2,1]

結果は、

[[1,2,1],[1,1,2],[2,1,1],[2,1,1],[1,1,2],[1,2,1]]

追記(2010.2.20) : zip でインデックスに相当するリストとくっつけるとき、以下のように書いていた。 (便宜的に関数名を zip’ とつける)

zip' xs = zip [0..(length xs)-1] xs

しかし、遅延評価により無限リストを使って以下のように書いた方がシンプル。

zip' = zip [0..]

すぐに忘れる脳みそのためのメモ

2008年9月29日月曜日