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@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 [EMAIL PROTECTED] 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 _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
