Cale Gibbard cgibbard at gmail.com
Wed Jul 13 11:13:10 EDT 2005

```Here's my little recursive solution:

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
>
> _______________________________________________