両替の組み合わせは?

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 のコインを1枚も使わない場合の組み合わせ。返ってくるリストには Nothing が混じっているから filterN で取り除いてやる。
  • (divide …) は kindsOfCoins のコインを1枚以上使う場合の組み合わせ。これは kindsOfCoins のコインを0枚以上使って (amount – faceOfCoin) を両替する場合の組み合わせのそれぞれに,kindsOfCoins を1枚追加して求めている。
  • 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

カテゴリー: Haskell パーマリンク

2 Responses to 両替の組み合わせは?

  1. IO () のコメント:

    (¥x -> x /= Nothing) は (/= Nothing) と書けます。
    Data.Maybe にはそのものスバリ isJust というのがあります。

  2. takatoh のコメント:

    ああ,やっぱりあるんですね。ライブラリの探索もやらんとなぁ。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください