[Haskell-cafe] Coin changing algorithm

Radu Grigore radugrigore at gmail.com
Wed Jul 13 11:29:59 EDT 2005


On 7/13/05, ChrisK <chrisk at mit.edu> wrote:

> Sort the list of integers, highest at the front of the list.
> (And perhaps remove duplicates with nub)

The first time I wrote in the comments that 'partition' takes a
"decreasing list of integers..." and then I decided to drop
"decreasing". Weakest precondition :)

> When you pop the first element you can already compute the range of
> quantity you will need, 

Is that really faster? I wouldn't be sure without profiling..

-- 
regards,
  radu
http://rgrig.blogspot.com/


More information about the Haskell-Cafe mailing list