[Haskell-cafe] Coin changing algorithm

[ChrisK]

Well, I don't have time to do more than comment, but here are few
improvements:

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

When you pop the first element you can already compute the range of
quantity you will need, and can perhaps special case when only zero
quantity will be permitted (untested):

partition (x:xs) m k  | x>m  = partition xs m k    -- x is too big

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.

Radu Grigore wrote:
> On 7/13/05, Dinh Tien Tuan Anh <tuananhbirm at hotmail.com> wrote:
> 
>>Any idea ?
> 
> 
> This is the first thing I wrote when i read your problem:
> 
> === begin integer_partition.lhs ===
> This is a solution to a question asked on Haskell cafe. The problem
> looks like a classical one.
> 
> You are given a list of positive integers and integers m and n.
> You are to find all multisets with at most k elements from the given list
> that sum up to m.
> 
> The idea is to write a recursive function that divides the problem into
> finding multisets with various maximal elements.
> 
> 
>>partition :: [Int] -> Int -> Int -> [[Int]]
> 
> 
> 
> The base case with exactly one solution
> 
> 
>>partition _ m _ | m == 0  = [[]]
> 
> 
> The base cases with no solution
> 
> 
>>partition [] _ _          = []
>>partition _  m _ | m < 0  = []
>>partition _  _ k | k <= 0 = []
> 
> 
> 
> Now we are prepared to attack the general case:
> 
> 
>>partition (x:xs) m k =
>>    (prefix x (partition (x:xs) (m-x) (pred k))) 
>>    ++
>>    (partition xs m k)
> 
> 
> The prefix function simply prepends a value to every list.
> 
> 
>>prefix :: Int -> [[Int]] -> [[Int]]
>>prefix x = map (\xs -> x:xs)
> 
> 
> Now, how to memoize this one? As is it is a SLOW solution.
> === end integer_partition.lhs ===
> 
>