直観的なプログラミング

順列の計算を Haskell でしたら、どうなるだろうか。n 個の異なった要素の中から m 個の相異なる要素を選び出した順列の個数(総数)はnPm と表される。すなわち

nPm = n * (n-1) * (n-2) * ... * (m-n+1)

だ。この定義では数値が降順に整列しているが、これを昇順に整列させると、

nPm = (m-n+1) * (m-n+2) * ... * (n-1) * n

となる。つまり(m-n+1) から n までの数列を全部かけたものが順列の個数になる。ここまで考えてくると、順列のプログラムは簡単だ。

permutation n m = product [(m-n+1)..n]

こんなに簡単なものは、Hugsのプロンプトから直接入力できる。

Hugs> p 5 3 where p n m = product [(n-m+1)..n]
60

同様に、組み合わせは nCm = nPm / m! だから、

Hugs> c 5 3 where c n m = product [(n-m+1)..n] `div` product [1..m]
10

変数への代入やループや条件判断などということを考えなくても、数列の向きを変えたり、途中で切ってみたりなど視覚的なイメージを操作しているうちにプログラムが出来上がってしまう。右脳的なイメージ操作をそのままプログラムに落としこめるという上で Haskell によるプログラミングはより直観的なものだと言えるのではないだろうか。
[PR]
by tnomura9 | 2009-08-09 05:59 | Haskell | Comments(0)
<< Haskell のすすめ クイックソート >>