[Haskell-cafe] Re: Coin changing algorithm
Yitzchak Gale
gale at sefer.org
Thu Jul 14 06:44:05 EDT 2005
Actually, something along the lines of Dinh's
attempted solution to the original partition
problem is a very nice solution to the coin
changing problem:
Make change for the amount a, using at most
k of the coins cs.
> coins _ 0 _ = [[]]
> coins _ _ 0 = []
> coins cs a k = [h:s | t <- init (tails cs),
> let h = head t,
> h <= a,
> s <- coins t (a-h) (k-1)]
(The functions "init" and "tails" are from the
Data.List module.)
Note that Dinh is already using a monad for his
solution, via Haskell's special syntax for the
List monad.
Here it is translated into regular monad syntax:
> coinsM _ 0 k = return []
> coinsM _ _ 0 = []
> coinsM cs a k = do
> t <- init (tails cs)
> let h = head t
> unless (h <= a) []
> s <- coinsM t (a-h) (k-1)
> return (h:s)
(The function "unless" is from the Control.Monad
module.)
-Yitz
More information about the Haskell-Cafe
mailing list