[Haskell-cafe] Coin changing algorithm
Radu Grigore
radugrigore at gmail.com
Wed Jul 13 10:42:59 EDT 2005
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/
More information about the Haskell-Cafe
mailing list