[Haskell] Can anyone help me with partition numbers?

Jan van Eijck Jan.van.Eijck at cwi.nl
Thu Nov 24 11:52:23 EST 2005

On Thu, Nov 24, 2005 at 07:59:50AM -0800, whoals (sent by Nabble.com) wrote:
>
> A partition of a positive integer n is a representation of n as the sum of any number of positive integral parts. For example, there are 7 partitions of the number 5: 1+1+1+1+1, 1+1+1+2, 1+1+3, 1+2+2, 1+4, 2+3 and 5. Define a function parts which returns the list of distinct partitions of an integer n. For example, parts 4 = [[1,1,1,1],[1,1,2],[1,3],[2,2],].
> --
> http://www.nabble.com/Can-anyone-help-me-with-partition-numbers--t612331.html#a1636283

> _______________________________________________

Like so:

generatePs :: (Int,[Int]) -> [[Int]]
generatePs (n,[])       = [take n (repeat 1)]
generatePs (n,(x:xs))   =
(take n (repeat 1) ++ (x:xs)) : generatePs (pack (x-1) ((n+x),xs))
where
pack :: Int -> (Int,[Int]) ->(Int,[Int])
pack 1 (m,xs) = (m,xs)
pack k (m,xs) = if k > m  then pack (k-1) (m,xs)
else           pack k     (m-k,k:xs)

parts :: Int -> [[Int]]
parts n | n < 1     = error "part: argument <= 0"
| n == 1    = []
| otherwise = generatePs (0,[n])

Let's hope this does not spoil a computer lab assignment ;-)

Jan

--
Jan van Eijck                                EMAIL jve at cwi.nl
CWI, PO Box 94079, 1090 GB Amsterdam, NL     phone +31-20-5924052 (work)
+31-20-6250735 (home)
WWW   http://www.cwi.nl/~jve                 fax   +31-20-5924200