Can anyone help me with partition numbers? Classic List Threaded 9 messages Open this post in threaded view
|

Can anyone help me with partition numbers?

 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],].
Open this post in threaded view
|

Re: Can anyone help me with partition numbers?

 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],]. > -- > 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 > [hidden email] > http://www.haskell.org/mailman/listinfo/haskellLike 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 [hidden email] 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 [hidden email] http://www.haskell.org/mailman/listinfo/haskell
Open this post in threaded view
|

Re: Can anyone help me with partition numbers?

 On Thu, Nov 24, 2005 at 05:52:23PM +0100, Jan van Eijck wrote: > 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]) How about a shorter version?     part :: Integer -> [[Integer]]     part = gen 1       where         gen m 0 = [[]]         gen m n = [ x:xs | x <- [m..n], xs <- gen x (n - x) ] Best regards Tomasz _______________________________________________ Haskell mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell
Open this post in threaded view
|

Re: Can anyone help me with partition numbers?

 Or (since we started to do someone's  homework anyway) generate 0 = [[]] generate n = [x:rest | x <- [1..n], rest <- generate (n-x)] Doaitse Swierstra On 2005 nov 25, at 10:29, Tomasz Zielonka wrote: > On Thu, Nov 24, 2005 at 05:52:23PM +0100, Jan van Eijck wrote: >> 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]) > > How about a shorter version? > >     part :: Integer -> [[Integer]] >     part = gen 1 >       where >         gen m 0 = [[]] >         gen m n = [ x:xs | x <- [m..n], xs <- gen x (n - x) ] > > Best regards > Tomasz > > _______________________________________________ > Haskell mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/haskell_______________________________________________ Haskell mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell
Open this post in threaded view
|

Re: Can anyone help me with partition numbers?

Open this post in threaded view
|

Re: Can anyone help me with partition numbers?

 In reply to this post by S. Doaitse Swierstra-2 Doaitse Swierstra wrote: > Or (since we started to do someone's  homework anyway) > > generate 0 = [[]] > generate n = [x:rest | x <- [1..n], rest <- generate (n-x)] Unless I am misled, this will generate the *unordered* partitions, e.g., for n=7, 64 of them, not 15. Jerzy Karczmarczuk _______________________________________________ Haskell mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell
Open this post in threaded view
|