Posts Tagged ‘intmap’

Programming Praxis – Partition Numbers

April 15, 2011

In today’s Programming Praxis exercise, our goal is to write a function to calculate partition numbers and to determine the 1000th partition number. Let’s get started, shall we?

Since the recursion in the algorithm is not as simple as in for example the Fibonacci numbers a simple zip will not suffice. To store previous results, we use an IntMap.

import Data.IntMap ((!), fromList, insert, findWithDefault)

Since we’re guaranteed to need every partition number below the one we’re looking for, we simply calculate all of them, starting from 1. This is done by folding over the numbers 1 through x with the IntMap as the accumulator.

partition :: Int -> Integer
partition x = if x < 0 then 0 else foldl p (fromList [(0,1)]) [1..x] ! x where
    p s n = insert n (sum [(-1)^(k+1) * (r pred + r succ) | k <- [1..n],
        let r f = findWithDefault 0 (n - div (k * f (3 * k)) 2) s]) s

Let’s see if we did everything correctly.

main :: IO ()
main = print $ partition 1000 == 24061467864032622473692149727991

Yup. After compiling it runs in about 0.4 seconds on my machine.