読者です 読者をやめる 読者になる 読者になる

bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

Haskell入門 リスト内包表記を利用して順列・組合せ問題に取り組む

1.好きになれなかった順列と組合せ

順列と組合せは高校生の時に学んだが、数学のほかの分野と異なり、これだけは孤立していて、また、その後の学問的発展も見られそうになかったので、興味のわかない分野であった。後に、確率・統計学も学ぶことになるが、これも同じような意味で好きになれない分野であった。

順列・組合せと確率・統計学はオペレーションズリサーチやパターン認識などの分野で有用になるのだが、未だに、好きになれない分野の一つである。

2.合コンした時のカップルへの期待

多くの人が体験し、楽しい思い出や、悲しい思い出を持っているであろう合コンを例にとって組合せの問題から考えることにする。今、男性3人、女性3人が出会ったとする。すべての人がカップルになれたとし、その時の組み合わせはどのようになるかをHaskellで解いてみる。

男性は1から3までの番号を女性は6から8までの番号がついていたとし、カップルを番号のタプルで表すことにする。その時の組み合わせは以下のようになる。

[(x,y) | x <- [1..3], y <- [6..8]]

これを実行すると、
[(1,6),(1,7),(1,8),(2,6),(2,7),(2,8),(3,6),(3,7),(3,8)]
が得られる。

組合せの数は、上記の要素を数えればよいのだが、Haskellには、リストの長さを教えてくれる関数lengthがあるので、それを用いる。

length [(x,y) | x <- [1..3], y <- [6..8]]

もちろん9が出力される。

それでは、男性の2番の人は女性8番の人とカップルになりたいと思っている。その時の組合せを求めてみる。2と8はすでに決まっているので、この2人を除いてのカップルを求めればよいので、次のようになる。

[(x,y) | x <- [1,3], y <- [6..7]]

これを実行すると、
[(1,6),(1,7),(3,6),(3,7)]
が得られる。

それでは、男性2と女性8がカップルになる確率を求める。これは、2と8を除いた時の組合せ数を全体の組合せ数で割ったあげればよい。

fromIntegral (length [(x,y) | x <- [1,3], y <- [6..7]]) / fromIntegral (length [(x,y) | x <- [1..3], y <- [6..8]])

上記のプログラムで、fromIntegralが気になることと思う。Haskellはとても型にうるさい言語である。今求めようとしているのは確率なので実数である。これに対して、lengthはリストの長さなので、整数である。整数を整数で割ったも実数を得ることはできないというのがHaskell流である。そこで、fromIntegralを用いて、整数にも実数にもなれる型に変えてしまう。

2.玉手箱からボールを取り出す

玉手箱には、赤、白、黄色、青、緑の五つのボールが入っているとし、そこから3つを順番に取り出すこととする。幾通りの並び方があるかを考える。これは順列の問題である。今、これらのボールに番号をつけ1から5とする。同じものが出てきてはいけないという条件を付けて、3回選ぶようにするとプログラムは次のようになる。

 [(x,y,z) | x <- [1..5], y <- [1..5],z <- [1..5], x /= y, x /= z, y /= z]

これの答えは次のようになる。
[(1,2,3),(1,2,4),(1,2,5),(1,3,2),(1,3,4),(1,3,5),(1,4,2),(1,4,3),(1,4,5),(1,5,2),(1,5,3),(1,5,4),(2,1,3),(2,1,4),(2,1,5),(2,3,1),(2,3,4),(2,3,5),(2,4,1),(2,4,3),(2,4,5),(2,5,1),(2,5,3),(2,5,4),(3,1,2),(3,1,4),(3,1,5),(3,2,1),(3,2,4),(3,2,5),(3,4,1),(3,4,2),(3,4,5),(3,5,1),(3,5,2),(3,5,4),(4,1,2),(4,1,3),(4,1,5),(4,2,1),(4,2,3),(4,2,5),(4,3,1),(4,3,2),(4,3,5),(4,5,1),(4,5,2),(4,5,3),(5,1,2),(5,1,3),(5,1,4),(5,2,1),(5,2,3),(5,2,4),(5,3,1),(5,3,2),(5,3,4),(5,4,1),(5,4,2),(5,4,3)]

数えるのが大変なので、lengthを用いて長さを求める。

 length [(x,y,z) | x <- [1..5], y <- [1..5],z <- [1..5], x /= y, x /= z, y /= z]

得られる答えは60である。