下降階乗羃と「組合せ型の最小完全ハッシュ関数」の逆関数

ふつうに組合せnCkをHaskellで書くとこうなります。数式は、n! / (k!・(n - k)!)です。

fact :: Int -> Int
fact n = product [1 .. n]

comb :: Int -> Int -> Int
comb n k = fact n `div` (fact k * fact (n - k))

これを下降階乗羃(falling factorial)を使って書くとこうなります。数式は、((n - 0)・(n - 1)…(n - (k - 1))) / ((k - 0)・(k - 1)…(k - (k - 1)))です。試してませんが、こっちの方が計算量が少なそうです。

ffact :: Int -> Int -> Int
ffact n k = product [(n - (k - 1)) .. n]

comb n k =  ffact n k `div` ffact k k

さて、これを使ってhttp://ja.doukaku.org/36/の問題を解いてみたいと思います。このRubyのプログラムを参考にHaskellで書いてみます。このRubyのプログラムは元々関数型のアプローチで書かれているので移植はとても楽です。

module Main (main) where
    
import Text.Printf (printf)

ffact :: Int -> Int -> Int
ffact n k = product [(n - (k - 1)) .. n]

comb :: Int -> Int -> Int
comb n k =  ffact n k `div` ffact k k

invCombHash :: Int -> Int -> Int -> [Int]
invCombHash 0 _ _ = []
invCombHash n k x =
    let c = comb (n - 1) k
    in if x >= c
       then 1 : invCombHash (n - 1) (k - 1) (x - c) 
       else 0 : invCombHash (n - 1) k x      

main :: IO ()
main = do
  let n = 5
      k = 2
  mapM_ (f n k) [0 .. (comb n k) - 1]
      where
        f n k x = printf "inv_comb_hash(%3d, %3d, %3d) = %s\n" n k x $ 
                    show $ invCombHash n k x
-- => inv_comb_hash(  5,   2,   0) = [0,0,0,1,1]
--    inv_comb_hash(  5,   2,   1) = [0,0,1,0,1]
--    inv_comb_hash(  5,   2,   2) = [0,0,1,1,0]
--    inv_comb_hash(  5,   2,   3) = [0,1,0,0,1]
--    inv_comb_hash(  5,   2,   4) = [0,1,0,1,0]
--    inv_comb_hash(  5,   2,   5) = [0,1,1,0,0]
--    inv_comb_hash(  5,   2,   6) = [1,0,0,0,1]
--    inv_comb_hash(  5,   2,   7) = [1,0,0,1,0]
--    inv_comb_hash(  5,   2,   8) = [1,0,1,0,0]
--    inv_comb_hash(  5,   2,   9) = [1,1,0,0,0]

下降階乗羃は最近読書中の「数学ガール」で知りました(気になる方は下のリンクを辿ってください。PDFもあります)。Haskellはいたるところに数学の匂いします。数学の問題を実際に動かして試す環境としては最高かも。
ミルカさんとコンボリューション

数学ガール (数学ガールシリーズ 1)