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

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).