[Haskell-beginners] partitions made of unique parts

[Daniel Fischer]

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)