[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],[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
More information about the Haskell
mailing list