Hatena::ブログ(Diary)

趣味的にっき このページをアンテナに追加 RSSフィード

2007-08-06

関連検索

関レレをGoogleで検索したら 22:35 関レレをGoogleで検索したらを含むブックマーク 関レレをGoogleで検索したらのブックマークコメント

関連検索が「しんや」「関レレ」でした。そんなに書いてたかな? 書いてたかも。コンスタントに毎月。。。

[] 下降階乗羃と「組合せ型の最小完全ハッシュ関数」の逆関数 22:09  下降階乗羃と「組合せ型の最小完全ハッシュ関数」の逆関数を含むブックマーク  下降階乗羃と「組合せ型の最小完全ハッシュ関数」の逆関数のブックマークコメント

ふつうに組合せ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

さて、これを使ってNothing found for 404 - エロと風俗情報満載 どう抜く?の問題を解いてみたいと思います。この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)

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

[] 与えられた数字のケタ数 22:30  与えられた数字のケタ数を含むブックマーク  与えられた数字のケタ数のブックマークコメント

Nothing found for 404 - エロと風俗情報満載 どう抜く?より。ふつうです。Integerを使ってIntの制限を越えられるようにしてみました。こういう場合は、Data.ListモジュールのgenericXXX関数を使います。

module Main (main) where

import Data.List (genericLength)

keta :: Integer -> (Integer, Integer)
keta n = let k = genericLength $ show n in (k, 10 ^ (k - 1))

main :: IO ()
main = mapM_ (print . keta) [2469, 600, 1]
-- => (4,1000)
--    (3,100)
--    (1,1)

[] 22:09 を含むブックマーク のブックマークコメント

20:00ごろ帰りました。