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],[4]]. -- Sent from the Haskell - Haskell forum at Nabble.com: http://www.nabble.com/Can-anyone-help-me-with-partition-numbers--t612331.htm...
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.htm...
_______________________________________________ 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 jve@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
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 = [[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
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 = [[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 Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
This does not work properly: Main> generate 5 [[1,1,1,1,1],[1,1,1,2],[1,1,2,1],[1,1,3],[1,2,1,1],[1,2,2],[1,3,1],[1,4],[2,1,1,1],[2,1,2],[2,2,1],[2,3],[3,1,1],[3,2],[4,1],[5]] You need to add something else: parts 0 = [[]] parts n = [m:p | m<-[1..n], p<-parts (n-m), (null p || m<=head p)] Main> parts 5 [[1,1,1,1,1],[1,1,1,2],[1,1,3],[1,2,2],[1,4],[2,3],[5]] Best, Salvador. 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)]
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 = [[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 Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
I apologize for the posting in which I mention the inadequacy of Doaitse Swierstra partition program, it has been commented by others, and the thread is obsolete. But my posting (issued immediately then) got delayed by the moderator because of the schizoidal nature of my e-mail address... Sorry. Jerzy Karczmarczuk
On Fri, Nov 25, 2005 at 10:29:48AM +0100, 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 = [[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
Brilliant! Jan -- Jan van Eijck EMAIL jve@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
participants (6)
-
Doaitse Swierstra -
Jan van Eijck -
Jerzy Karczmarczuk -
Salvador Lucas -
Tomasz Zielonka -
whoals (sent by Nabble.com)