日: 2006年5月12日

両替の組み合わせは？

id:a-san さんの両替するのに何通りあるか？に刺激されて，両替の組み合わせを列挙する enumChange をつくってみた。Maybe の扱いでちょっと苦労したよ。

　cf. http://d.hatena.ne.jp/a-san/20060508#p1

enumChange coins amount = map peel (cc amount 0)
    where
        cc amount kindsOfCoins
            | amount == 0 = [Just []]
            | (amount < 0) = [Nothing] | kindsOfCoins >= length coins = [Nothing]
            | otherwise =
                filterN ((cc amount (kindsOfCoins + 1)) ++
                       (divide faceOfCoin (cc (amount - faceOfCoins) kindsOfCoins)))
            where
                faceOfCoin = coins !! kindsOfCoins

divide a = map divide'
    where
        divide' x = case x of
            Just m -> Just (a:m)
            Nothing -> Nothing

filterN list = filter (\x -> x /= Nothing) list

peel x = case x of
             Just m -> m
             Nothing -> error "`Nothing' is found."

実行。

*Main> enumChange [10,5,1] 10
[[1,1,1,1,1,1,1,1,1,1],[5,1,1,1,1,1],[5,5],[10]]
*Main> length $ enumChange [10,5,1] 10
4

countChange は id:a-san さんのもの。

*Main> length $ enumChange [500,100,50,10,5,1] 100
159
*Main> countChange [500,100,50,10,5,1] 100
159
*Main> length $ enumChange [50,25,10,5,1] 100
292
*Main> countChange [50,25,10,5,1] 100
292
*Main> enumChange [500,100,50,10,5,1] 100
[[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[5,
5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1],[5,5,5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[5,5,5,5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
（以下略）

いけてるみたいだな。

以下，自分用のメモ。

  • cc は両替したコインの組み合わせのリストを返す。
  • amount == 0 ならうまくいった組み合わせなので，リストの終端としての空リストを返す。
  • (amont < 0)，kindsOfCoins >= length coins のときはその組み合わせがうまくいかないときなので Nothing。
  • (cc amount (kindsOfCoins + 1)) は kindsOfCoins のコインを１枚も使わない場合の組み合わせ。返ってくるリストには Nothing が混じっているから filterN で取り除いてやる。
  • (divide …) は kindsOfCoins のコインを１枚以上使う場合の組み合わせ。これは kindsOfCoins のコインを０枚以上使って (amount – faceOfCoin) を両替する場合の組み合わせのそれぞれに，kindsOfCoins を１枚追加して求めている。
  • cc の返すリストは Maybe [a] のリストだから peel で Maybe をはずす。

追記：
Data.Maybe に catMaybes という関数があった。わざわざ peel を作んなくてもよかったのか。
GHCi で使うなら :module Data.Maybe，プログラムで使うなら import Data.Maybe しておく。

Prelude Data.Maybe> :type catMaybes
catMaybes :: [Maybe a] -> [a]
Prelude Data.Maybe> catMaybes [Just 1, Just 2, Just 3]
[1,2,3]

Nothing は無視してくれるみたいだ。

Prelude Data.Maybe> catMaybes [Just 1, Nothing, Just 3]
[1,3]

ってことは filterN もいらないのか……orz

パスカルの三角形

id:hyuki さんのを見て。

　cf. http://sicp.g.hatena.ne.jp/hyuki/20060512/pascal

といっても Scheme はよくわからんので Ruby版（id:rubyco:20060429:pascal）を見ながら書いた。

combination n k | k == 1 = 1
                | k == n = 1
                | otherwise = (combination (n-1) k) + (combination (n-1) (k-1))

line n = map (combination n) [1..n]

pascalTriangle = do mapM putStrLn (map (show . line) [1..10])

実行。

*Main> pascalTriangle
[1]
[1,1]
[1,2,1]
[1,3,3,1]
[1,4,6,4,1]
[1,5,10,10,5,1]
[1,6,15,20,15,6,1]
[1,7,21,35,35,21,7,1]
[1,8,28,56,70,56,28,8,1]
[1,9,36,84,126,126,84,36,9,1]