Re: [Haskell-cafe] Coin changing algorithm

13 Jul 2005


      Here's mine, which is similar to Cale's, although done before I saw his:

coins = reverse [1,5,10,25]

change' 0 = [[]]
change' amt =
    concat $ map subchange $ filter (amt >=) coins
    where
        -- recursively make change
        subchange c =
            map (\l -> c:l) $ filter (canon c) $ change' (amt - c)

        -- filter change lists to those in some canonical order
        -- this ensures uniqueness
        canon _ [] = True
        canon c (x:xs) = c <= x

change amt num = filter (\l -> length l <= num) $ change' amt

Re: [Haskell-cafe] Coin changing algorithm

Kurt