The following function finds all the partitions of an integer that are made of unique parts. It works, but I'm not happy with it--seems too complex. Is there a more haskelly (clever) way to implement this? -- parts n finds all the partitions of n having unique parts -- helper function parts' n r m finds partitions of n from a set r of remaining possible parts, -- with a minimum part of m. parts n = parts' n [1..n] 1 where parts' 0 _ _ = [[]] -- there's always one way ([]) to get a sum of 0 parts' n [] _ = [] -- if n /= 0, there are no possible partitions of the empty list parts' n remaining atleast = [(x:y) | x <- filter (>= atleast) remaining, y <- (parts' (n-x) (remaining \\ [x])) x] *Main> parts 11 [[1,2,3,5],[1,2,8],[1,3,7],[1,4,6],[1,10],[2,3,6],[2,4,5],[2,9],[3,8],[4,7],[5,6],[11]]
Am Samstag 29 August 2009 17:43:02 schrieb I. J. Kennedy:
The following function finds all the partitions of an integer that are made of unique parts. It works, but I'm not happy with it--seems too complex. Is there a more haskelly (clever) way to implement this?
-- parts n finds all the partitions of n having unique parts -- helper function parts' n r m finds partitions of n from a set r of remaining possible parts, -- with a minimum part of m.
parts n = parts' n [1..n] 1 where parts' 0 _ _ = [[]] -- there's always one way ([]) to get a sum of 0 parts' n [] _ = [] -- if n /= 0, there are no possible partitions of the empty list parts' n remaining atleast = [(x:y) | x <- filter (>= atleast) remaining, y <- (parts' (n-x) (remaining \\ [x])) x]
*Main> parts 11 [[1,2,3,5],[1,2,8],[1,3,7],[1,4,6],[1,10],[2,3,6],[2,4,5],[2,9],[3,8],[4,7] ,[5,6],[11]]
You don't have to have a list of possible parts, the possible parts follow from the minimum: parts :: Int -> [[Int]] -- or (Num a, Ord a) => a -> [[a]] parts 0 = [[]] parts n | n < 0 = [] | otherwise = mpart n 1 where -- mpart m k partitions m into distinct parts of size at least k mpart m k | m < k = [] | m <= 2*k = [[m]] | otherwise = map (k:) (mpart (m-k) (k+1)) ++ mpart m (k+1)
Am Samstag 29 August 2009 17:43:02 schrieb I. J. Kennedy:
The following function finds all the partitions of an integer that are made of unique parts. It works, but I'm not happy with it--seems too complex. Is there a more haskelly (clever) way to implement this?
-- parts n finds all the partitions of n having unique parts -- helper function parts' n r m finds partitions of n from a set r of remaining possible parts, -- with a minimum part of m.
parts n = parts' n [1..n] 1 where parts' 0 _ _ = [[]] -- there's always one way ([]) to get a sum of 0 parts' n [] _ = [] -- if n /= 0, there are no possible partitions of the empty list parts' n remaining atleast = [(x:y) | x <- filter (>= atleast) remaining, y <- (parts' (n-x) (remaining \\ [x])) x]
*Main> parts 11 [[1,2,3,5],[1,2,8],[1,3,7],[1,4,6],[1,10],[2,3,6],[2,4,5],[2,9],[3,8],[4,7],[5,6],[11]]
Another thing: In your list of possible parts, you keep values smaller than the minimum value and values larger than the remaining value to be partitioned. This leads to horrible performance (1 second to partition 20 and 20 minutes to partition 30 on my box) since you have to scan through unnecessarily long lists and you try to partition negative numbers. In particular the latter cripples performance, inserting a guard parts' n remaining atleast | n < 0 = [] | otherwise = [(x:y) | x <- filter (>= atleast) remaining , y <- (parts' (n-x) (remaining \\ [x])) (x)] into the last clause of parts' brings the time for parts 30 down to 0.06 seconds, for parts 70 to 2.06 seconds :) (still about 100 times slower than the code from my previous post).
participants (2)
-
Daniel Fischer -
I. J. Kennedy