Posts Tagged ‘partitions’

Programming Praxis – Prime Partitions

October 19, 2012

In today’s Programming Praxis exercise, our goal is to calculate the number of prime partitions for a given number. Let’s get started, shall we?

Some imports:

import Data.List
import qualified Data.Map as M
import Data.Numbers.Primes

First we need to calculate the sum of the unique prime factors of a given number. The trivial way is to to take the list of prime factors, filter out the unique numbers and sum those. In the provided solution this is marked as the wrong way since there is a more efficient solution. On the other hand, we only need to this once each for the numbers 1 through 1000, so it’s not like it’s a massive performance bottleneck. Since performance doesn’t matter much, I personally prefer the straightforward, easy to understand implementation.

sopf :: Integer -> Integer
sopf = sum . nub . primeFactors

At first glance, the algorithm for the amount of prime partitions bears some resemblance to the Fibonacci function. The difference here is that each term refers to all of its predecessors instead of a fixed number, which means the typical zipWith solution won’t work. Instead, we build op a dictionary where for each number we store sopf(n) and k(n) so we don’t have to recalculate them.

k :: Integer -> Integer
k n = snd $ foldl' calc M.empty [1..n] M.! n where
    calc dict i = M.insert i (s, div (s + sum (map (\j -> (fst $ dict M.! j) *
        (snd $ dict M.! (i - j))) [1..i-1])) i) dict where s = sopf i

A test to see if everything is working properly:

:: IO ()
main = print $ k 1000 == 48278613741845757

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