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)