順列

先ず、リストの順列を作る関数を perm という名前にする。xs というリストがあったとき、perm xs は xs を並べ替えたリストのリストである。これを型シグネチャーであらわすと次のようになる。

perm :: [a] -> [[a]]

Haskell で関数を定義するときは、関数の型を決めておいたほうが作りやすい。

次に、リストの並べ替えのアルゴリズムを見つける。例えば、リスト [1, 2, 3] があったとき順列にはどのようなものがあるだろうか。まず、最初に３つの要素のうち一つを取り出す。この操作は Haskell のリスト内包表記では次のように書ける。

Prelude Data.List> [x | x <- [1,2,3]]
[1,2,3]

これは、リスト [1, 2, 3] の要素をひとつ取り出す方法が３つあることを示している。

順列の場合にはこれらの先頭の要素に続く要素の並びを見つけないといけない。例えば先頭が 1 であったとする。1 の後ろにはリストのうち 1 以外の要素のリスト [2, 3] の順列が続く。[2, 3] の順列のリストは [2, 3] と [3, 2] の２つがあるが、これをリストにまとめたものは [[2,3], [3,2]] で、これは perm [1, 2] で表すことができる。 先頭の 1 と 1 以外の要素をつなげると、順列のうち先頭が 1 のもののリストができる。

Prelude Data.List> [x:ys | x <- [1], ys <- [[2,3],[3,2]]]
[[1,2,3],[1,3,2]]

これを先頭が 1 以外の場合にも当てはまるように抽象化してみよう。リストを xs として、perm 関数を用いてこの関係を表すと次のようになる。

Prelude Data.List> perm xs = [x:ys | x <- xs, ys <- perm (delete x xs)]

delete 関数はリスト xs から x を取り除いたリストを作る。だいぶ形になってきたが、これは再帰的定義の recursive case なので、これだけでは動かない。base case が必要だ。

それはリストが空の場合を考えるとよい。これは perm [] であるが、perm の型から [[]] でなければならないことが分かる。つまり空のリストを並べ替えても空のリストが１つだけできるだけだ。

これを上の recursive case と組み合わせると perm の定義は次のようになる。

Prelude Data.List> perm [] = [[]]; perm xs = [x:ys | x <- xs, ys <- perm (delete x xs)]

実行例は次のようになる。

Prelude Data.List> perm [1,2,3]
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

リストの要素すべてを並べるのではなく、そのうちの何個かを並べる場合は次のようにする。

Prelude Data.List> nub $ map (take 2) $ perm [1,2,3,4]
[[1,2],[1,3],[1,4],[2,1],[2,3],[2,4],[3,1],[3,2],[3,4],[4,1],[4,2],[4,3]]

nub 関数は重複した要素を一つにまとめてしまう関数だ。

組み合わせ

組み合わせはリストの要素のうち数個を取り出す方法は何通りかという考え方をするが、ここでは、何個でも取り出すやり方をすべて考えることにする。これは、集合の冪集合を求めることと同じなので関数名を pow にする。pow の型シグネチャーは次のようになる。

pow :: [a] -> [[a]]

pow のアルゴリズムはどうなるだろうか。リストのパターンを (x:xs) とする。x は先頭の要素で、xs はそれ以外の要素のリストだ。pow は x を含む組み合わせと、含まない組み合わせを合わせたものだ。したがって、次のように表すことができる。

pow (x:xs) = map (x:) (pow xs) ++ pow xs

また、上の定義は recursive case なので、base case に pow [] = [[]] が必要だ。

Prelude Data.List> pow [] = [[]]; pow (x:xs) = map (x:) (pow xs) ++ pow xs
Prelude Data.List> pow "abc"
["abc","ab","ac","a","bc","b","c",""]

リストのうち何個かを取り出す組み合わせは、冪集合のうち個数を指定したものになる。

Prelude Data.List> filter (\x-> length x == 2) $ pow "abc"
["ab","ac","bc"]

これは、組み合わせの個数を指定する参考書に見られるものとは違うが、コードが単純になる。