Archive for May, 2012

Programming Praxis – Streaming Knapsack

May 15, 2012

In today’s Programming Praxis exercise, our goal is to write that a function that gives the first possible knapsack, i.e. the first combination of k values that sum up to a given value n, from a lazy list. The list should not be evaluated further than necessary. Let’s get started, shall we?

Some imports:

import Data.List
import Debug.Trace
import System.IO

Rather than constructing a matrix we use a solution that probably isn’t as efficient, but significantly more compact and easy to understand. Just take all possible combinations of numbers and find the first one of length k that sums up to n.

knapsack :: Num a => Int -> a -> [a] -> Maybe [a]
knapsack k n = find (\s -> length s == k && sum s == n) . subsequences

To demonstrate that the function is indeed lazy, we apply it to a list that indicates when one of its elements is evaluated. The hFlush is to make sure the result of the first function is printed before the second list gets evaluated, since without it the two results will be printed at the end.

main :: IO ()
main = do print . knapsack 7 37 $ map debugEval [1..20]
          hFlush stdout
          print . knapsack 7 17 $ map debugEval [1..20]
    where debugEval n = trace ("evaluated: " ++ show n) n
Advertisements

Programming Praxis – Partitions

May 11, 2012

In today’s Programming Praxis exercise, our goal is to write a function that gives all unique sums that produce a given number. Let’s get started, shall we?

The function is fairly trivial. We avoid duplicates by allowing only equal or decreasing series of numbers.

part :: Int -> [[Int]]
part 0 = [[]]
part n = [x:y | x <- [1..n], y <- part (n-x), [x] >= take 1 y]

A quick test to see if everything is working properly:

main :: IO ()
main = mapM_ print $ part 6