[Haskell-cafe] Coin changing algorithm

[Cale Gibbard]

Here's my little recursive solution:

import Monad
import List

makeChange :: [Integer] -> Integer -> Integer -> [[Integer]]
makeChange coins amount maxCoins
    | amount < 0  = []
    | amount == 0 = [[]]
    | null coins  = []
    | amount `div` maximum coins > maxCoins = [] -- optimisation
    | amount > 0  =
        do x <- coins
           xs <- makeChange (filter (<= x) coins)
                            (amount - x)
                            (maxCoins - 1)
           guard (genericLength (x:xs) <= maxCoins)
           return (x:xs)

makeChange' :: Integer -> Integer -> [[Integer]]
makeChange' amount maxCoins = makeChange coins amount maxCoins
    where coins = [200,100,50,20,10,5,2,1]

 -- Cale

On 13/07/05, Dinh Tien Tuan Anh <tuananhbirm at hotmail.com> wrote:
> 
>   Hi,
> The problem is:
> Given an amount of money m, and unlimited coins of value 1p, 2p, 5p, 10p,
> 20p, 50p, £1 and £2
> List ALL (distinct) ways  of change for m, using no greater than k coins
> 
> eg: m = 75, k = 5
>      =>   [50, 20, 5]
>              [50, 20, 1,2,2]
>             ..........
>             .........
> 
> i have been familiar with the "integer parition" problem, but how to
> generalise to solve the one above ?
> 
> Is this problem suitable for functional programming language ?
> 
> Any idea ?
> Cheers
> 
> _________________________________________________________________
> It's fast, it's easy and it's free. Get MSN Messenger 7.0 today!
> http://messenger.msn.co.uk
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>