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.

### Like this:

Like Loading...

*Related*

Tags: bonsai, code, Haskell, intmap, kata, numbers, partition, praxis, programming

This entry was posted on April 15, 2011 at 11:56 am and is filed under Programming Praxis. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply