Haskellで遊ぶよ

Haskell で「ある金額になるコインの組み合わせ」

07:13

ちょうど良さそうな問題があったので、かなーり久々に Haskell してみる。

ある金額になるコインの組み合わせ数とその組み合わせを全て答え下さい。

条件）

・コインの種類は自由に設定できるようにする。

・順序が違うだけのものは一つの組み合わせとする。

　（例：16の組み合わせで、[1, 5, 10]と[10, 5, 1]は同じ）

例）

コインの種類：1, 5, 10, 50, 100, 500

金額：10

組み合わせ数：4

組み合わせ：

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

[1, 1, 1, 1, 1, 5]

[5, 5]

[10]

お題：ある金額になるコインの組み合わせ - No Programming, No Life

import List (sort)

solveCoin :: Integer -> [Integer] -> [[Integer]]
solveCoin total coins = 
  let coins' = reverse $ sort coins
  in takeCoins coins' [] total

takeCoins :: [Integer] -> [Integer] -> Integer -> [[Integer]]
takeCoins [] _ _ = []
takeCoins cs xs rest = 
  let c = head cs
      cs' = tail cs
      possibleCombinations = case signum (rest - c) of
        -1 -> []
        0 -> [c:xs]
        1 -> takeCoins cs (c:xs) (rest - c)
  in possibleCombinations ++ (takeCoins cs' xs rest)

main = print $ solveCoin 10 [1, 5, 10, 50, 100, 500]

↓実行結果。

10],[5,5],[1,1,1,1,1,5],[1,1,1,1,1,1,1,1,1,1?

http://codepad.org/9cDnkcPt

「コインの組み合わせ数」と「その組み合わせを全て」を答えないといけないんだけど、「コインの組み合わせ数」は出力省略してる。

もっと簡単になるのかもしれないけど僕の実力ではここまでだった。あとは () じゃなくて $ を使うぐらいしか思いつかない。