Re: [Haskell-cafe] Coin changing algorithm

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 Reply-To: Kurt To: haskell-cafe@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@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