組合せ in Haskell

id:Ozy:20060603#p2
id:Ozy:20060604#p1から。

何となく気になったんで、Haskellで実装。……まあもっと簡単になるとは思うけど。

以下、組合せを求めるのに必要な部分のみ抜粋。

dfoldl _ z [] _  = z
dfoldl _ z _  [] = z
dfoldl f z (x:xs) (y:ys) = dfoldl f (f z x y) xs ys
comb :: (Integral a) => a -> a -> a
comb _ 0 = 1
comb n r = dfoldl (?x a b -> x * b `div` a) 1 (take (fromIntegral r2) [1..]) (take (fromIntegral r2) [n,n-1..1]) where r2 = if r > (n `div` 2) then n - r else r

303Byte。長っ！……まあ、長さはそんなに気にしてないんで、良いです。
苦心したのが、(fromIntegral r2)の部分。こうしないと、Intの範囲オーバーフローして負数とかが出て来て吃驚しちゃう。

実行結果

$ ./comb 6 2
15

$ ./comb 1000 100
63850511926305130236698511142022274281262900693853331776286816221524376994750901948920974351797699894319420811933446197797592213357065053890

故レックライあっという間に計算してしまう。しかも値は正確。いいねえ。

工夫したところ

• dfoldlと言う関数を定義してみた
  • foldlのリスト二つ版、とでも云いましょうか。

気になるところ

• 長い。
• dfoldlを別ので代替できないか

ところで、PKUってなんなんでしょう？