[Haskell-beginners] partitions made of unique parts

I. J. Kennedy jack at realmode.com
Sat Aug 29 11:43:02 EDT 2009


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]]


More information about the Beginners mailing list