ちょうど良さそうな問題があったので、かなーり久々に 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
「コインの組み合わせ数」と「その組み合わせを全て」を答えないといけないんだけど、「コインの組み合わせ数」は出力省略してる。
もっと簡単になるのかもしれないけど僕の実力ではここまでだった。あとは () じゃなくて $ を使うぐらいしか思いつかない。