組み合わせ

リストの要素からn個を取り出す組み合わせを列挙する Haskell プログラム。プログラミング玉手箱からの引用。組み合わせの列挙をちょっと知りたいと思うときがあるが、下のプログラムなら短いので使い捨てプログラムとしては最適。

用例:
Main> comb "abcde" 3
["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]

Main> comb ["portion", "sword", "dagger", "magic", "shield"] 3
[["portion","sword","dagger"],["portion","sword","magic"],["portion","sword","shield"],["portion","dagger","magic"],["portion","dagger","shield"],["portion","magic","shield"],["sword","dagger","magic"],["sword","dagger","shield"],["sword","magic","shield"],["dagger","magic","shield"]]

プログラム:
comb :: [a] -> Int -> [[a]]
comb _ 0     = [[]]
comb [] _     = []
comb (x:xs) n = map (x:) (comb xs (n-1)) ++ comb xs n

例によって再帰関数による定義がなされている。上の2行3行は終了条件なので、最下段の4行目の意味を理解すればこのプログラムを解読できる。

こういう問題を考えるときはモデルを作って考えるとよい。今仮にリスト[a, b, c, d, e] のうちから3個だけをとる組み合わせのやり方を考えてみよう。机の上に a, b , c, d, e の文字を書き込んだカードが5枚並んでいるとする。次のような並べ方だ。

[a] [b] [c] [d] [e]

これらのカード五枚から3枚とるとき何通りの取り方があるかというのが問題だ。最初の選択としては、どのカードを一枚選びだすかということになる。最初に [a] にする場合、[b] にする場合、... と選択肢は5つあり、それぞれについて、残りのカードが異なるから結局、5×4×3 = 60 通りの並べ方が存在する。

ところが、組み合わせの場合は順列では違っていても組み合わせとしては同じというものがある。たとえば abc と acb は順列としては違うが組み合わせとしては同じものだ。したがって上の考え方は残念ながら使えない。

ところが、上のカードの並び方を変えずに、どのカードを取るか取らないかという選び方をすると、順列の変更がないのでその選び方がそのまま組み合わせの方法になる。この並び方を変えないでカードを引き出すだけというモデルで考えることにすると上の再帰関数の意味がよくわかるようになる。

それではどういうふうに考えると再帰関数をつくることができるだろうか。

まず上のカードの左端の [a] のカードに注目する。仮に上の五枚のカードから3枚抜き出すやり方を集めたリストが comb "abcde" 3 で与えられたとしよう。ここで comb "abcde" 3 の中で a を含んでいるものと、a を含まないものとを考えることができる。そうすると comb "abcde" 3 は次の map (a:) (comb "bcde" 2) と comb "bcde" 3 の二つの部分集合に分けられる。

これでは分かりにくいのでもっと具体的に展開すると、

map (a:) (comb "bcde" 2)
= map (a:) ["bc", "bd", "be", "cd", "ce", "de"]
= ["abc", "abd", "abe", "acd", "ace", "ade"]

comb "bcde" 3
= ["bcd", "bce", "bde", "cde"]

したがって、

comb "abcde" 3 = map (a:) (comb "bcde" 2) ++ comb "bcd" 3

となることが分かる。右側の式では、最初の再帰式では引数のリストが "bcde" 2 で、二番目の comb の引数が "bcde" 3 で第2引数の整数の値が一つ大きいのに注目してほしい。これは、2番目の comb では a を採用していないのであと3枚カードを引くことができるからだ。一方一番目の comb では、すでに a を採用しているのであと二枚しか選べない。

また、comb が返す値がまだ分かっていないのにすでに分かっているものとして式を組み立てているのも重要だ。差分だけをきちんと定義すれば元の関数の計算はコンピュータが計算してくれるからだ。

これを一般的な再帰式に表したのが上のプログラムだ。

comb (x:xs) n = map (x:) (comb xs (n-1)) ++ comb xs n

左辺の第一引数のパターン (x:xs) は左端の要素を取り出して処理することを示している。右辺の map (x:) は左端の要素を採用しそれを comb xs (n-1) のすべての要素の先頭につなげることを示している。comb xs (n-1) は左端の要素 x を取り除いた残りのリスト xs から (n-1) 個選び出したリストのリストだ。また、comp xs n は左端の要素 x を取らなかった場合で、x を除いた残りの文字列から n 個選び出すことを示している。

こういうものは文字で表現すると非常にわかりにくくなるので、頭の中でカードを引いたり戻したりして納得しなければならない。Haskell のプログラムの分かりにくさと作りやすさの秘密はここにある。Haskell では言葉よりも直接的に頭の中のイメージを表現できるのだ。

Haskell が非常にコンパクトなプログラムを作ることができる一方、解読するほうは暗号解読のような操作を要求される。しかし、イメージをそのままプログラムにできるというHaskell の性質に慣れると、暗号解読の負担は逆に言葉よりも直接的にアイディアを表現できる手段となる。

Haskell のイメージを直接に表現する力は暗号的なプログラムとなって、取りつきにくい印象を与えるが、これも慣れの問題で、頭の中のビジュアルなイメージをそのままプログラムにできて、しかも、それが動いてしまうという体験は、たとえ初歩的なプログラムを作っていても十分に楽しい経験となる。
[PR]
by tnomura9 | 2009-09-07 07:00 | Haskell | Comments(0)
<< 勝間和代を目指さない 乱数発生器 >>