[Haskell-cafe] Coin changing algorithm

[ChrisK]

Okay, I like Cale's extra guard short circuit so much I must add it to
my pseudo-example.

Cale's guard:
> amount `div` maximum coins > maxCoins = [] -- optimisation

Mine, updated.
> 
> partition (x:xs) m k  | x>m  = partition xs m k    -- x is too big
>
> parititon (x:_) m k   | x*k < m = []               -- cannot succeed
> 
> partition (x:xs) m k  | otherwise =
>      let most = min k (div m x)
>          range = [most,most-1..1]
>          use quantity = (\quantity -> prefix (replicate quantity x)
> (partition xs (m-quantity*x) (k-quantity))
>      in map use range
> 
> The first result from this will be the greediest.

As for memoizing, it would be interesting to attack it differently.

Get all the results for a given m and unlimited k and store them sorted
by k.  Then return the list via takeWhile length up to k.  Next call for
same m can skip to the takeWhile and be very fast.

Pre-generating the table for amounts up to some limit could be done more
efficiently with a bottom up approach.

-- 
Chris