partitions made of unique parts

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

partitions made of unique parts

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]]
Reply | Threaded
Open this post in threaded view
|

partitions made of unique parts

Daniel Fischer-4
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)

Reply | Threaded
Open this post in threaded view
|

partitions made of unique parts

Daniel Fischer-4
In reply to this post by I. J. Kennedy
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).