[Haskell-beginners] partitions made of unique parts
Daniel Fischer
daniel.is.fischer at web.de
Sat Aug 29 13:39:42 EDT 2009
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).
More information about the Beginners
mailing list