[Haskell-cafe] Coin changing algorithm

[Radu Grigore]

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 ===


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