{-
Program ...... : partition.hs (Partitions of Integers)
Partitions of Integers using generating function
Author ....... : David Tran
Date ......... : 2008-10-25
References ... : http://en.wikipedia.org/wiki/Partition_%28number_theory%29
http://chowkafat.net/Enumeration15.html
========================================================================
Here shows example for n == 3
* To simply the calculation, the coefficient of term x^0 is always ([],0)
* most time we are interested only on term "n" (limited constant).
So any term > n is no need to calculate;
that's the "max" for; so we will not have an infinity of terms Polynomial.
term 3 1 = [ ([],0), ([(1,1)],1), ([(1,2)],2), ([(1,3)], 3) ]
= ( 1 x^0 + (N1 x)^1 + (N1 x)^2 + (N1 x)^3 )
term 3 2 = [ ([],0), ([(2,1)],2) ]
= ( 1 x^0 + (N2 x)^1 )
term 3 3 = [ ([],0), ([(3,1)],3) ]
= ( 1 x^0 + (N3 x)^1 )
multiple the 3 terms = (term 3 1) * (term 3 2) * (term 3 3)
mult 3 (term 3 3) $ mult 3 (term 3 1) (term 3 2)
= [ ([],0), ([(2,1)],2), ([(1,1)],1), ([(1,1),(2,1)],3),
([(1,2)],2), ([(1,3)],3), ([(3,1)],3) ]
([(1,1),1) is for term x^1 => (1,1) => 1 = 1
for term x^2, we got [(2,1)] and [(1,2)] => 2 = 2 = 1+1
for term x^3, [(1,1),(2,1)], [(1,3)], [(3,1)] => 3 = 1 + 2
= 1 + 1 + 1
= 3
========================================================================
Example Usage:
*Main> partition 5
[[(5,1)],[(2,1),(3,1)],[(1,1),(4,1)],[(1,1),(2,2)],[(1,2),(3,1)],[(1,3),(2,1)],[(1,5)]]
*Main> pp_partition 5
5=5
5=2+3
5=1+4
5=1+2+2
5=1+1+3
5=1+1+1+2
5=1+1+1+1+1
*Main> countPartition 5
7
-}
type Constant = (Int, Int) -- "Constant" at "Position"
type Coefficient = [ Constant ] -- "Sum" of Constant
type Exponent = Int
type Term = (Coefficient, Exponent)
type Polynomial = [ Term ] -- "Sum" of Term
term :: Int -> Int -> Polynomial
term max n = ([],0) : [ ([(n,i)], n * i) | i <- [1.. max `div` n ] ]
mult :: Int -> Polynomial -> Polynomial -> Polynomial
mult max p1 p2 = [ (c1++c2, e1+e2) | (c1,e1) <- p1, (c2,e2) <- p2, e1+e2 <= max ]
partition :: Int -> [ Coefficient ]
partition n = only_coeff $ filter_terms $ generate_terms
where generate_terms = foldr1 (mult n) (map (term n) [1..n])
filter_terms = filter (\(c, e) -> e == n)
only_coeff = map (\(c, e) -> c)
countPartition :: Int -> Int
countPartition = length . partition
pp_partition :: Int -> IO() -- pretty print partition
pp_partition n = sequence_ $ map showSum (partition n)
where showSum s = do putStr $ (show n) ++ "=" ++ sumList (strList s) ++ "\n"
strList = foldl (\acc (n,i) -> acc ++ replicate i (show n)) []
sumList = foldl1 (\x y -> x ++ "+" ++ y)
This entry was posted
on Saturday, November 21st, 2009 at 8:16 am and is filed under Haskell.
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.