[Haskell] Can anyone help me with partition numbers?

[Jan van Eijck]

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],[4]].
> --
> Sent from the Haskell - Haskell forum at Nabble.com:
> http://www.nabble.com/Can-anyone-help-me-with-partition-numbers--t612331.html#a1636283

> _______________________________________________
> Haskell mailing list
> Haskell at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell

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    = [[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