On 7/13/05, Dinh Tien Tuan Anh
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/