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
