[Haskell-cafe] Coin changing algorithm

[Dinh Tien Tuan Anh]

Thanks for all your solutions
It seems that recursion is the only way.
i thought it is a variation of the "integer parition" problem so that can be 
solved linearly (by generating next solution in (anti)lexicographic order)

i guess i have to learn Monads then, ^_^

Cheers



>From: Kurt <kelanslists at gmail.com>
>Reply-To: Kurt <kelanslists at gmail.com>
>To: haskell-cafe at haskell.org
>Subject: Re: [Haskell-cafe] Coin changing algorithm
>Date: Wed, 13 Jul 2005 11:19:03 -0400
>
>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
>_______________________________________________
>Haskell-Cafe mailing list
>Haskell-Cafe at haskell.org
>http://www.haskell.org/mailman/listinfo/haskell-cafe

_________________________________________________________________
Winks & nudges are here - download MSN Messenger 7.0 today! 
http://messenger.msn.co.uk