[Haskell-cafe] Re: partitions of a multiset

[Brent Yorgey]

On 7/24/07, Pekka Karjalainen <p3k at iki.fi> wrote:
>
> On 7/24/07, Brent Yorgey <byorgey at gmail.com> wrote:
> > given a list L :: [a], I'm looking for all partitions P :: [[a]] where
> (sort
> > . concat $ P) == (sort L).
>
> Here is quick attempt that requires Ord [a] and expects a sorted list.
> It may very well not be correct, but it seemed to get all the simple
> cases I tried right. Can you find a counterexample where it doesn't
> work?
>
> import Data.List (nub, (\\))
>
> subsets [] = [[]]
> subsets xs = []:[ a:b | a <- nub xs,
>   let (_:tl) = dropWhile (/=a) xs, b <- subsets tl ]
>
> multiPart [] = [[]]
> multiPart xs = [ a:b | a <- takeWhile ((head xs ==) . head) $ tail $
>   subsets xs, b <- multiPart $ xs \\ a, null b || a <= head b ]


very nice!  I had an inkling that the solution would depend on an ordering
of subsets, but I hadn't come up with the right way to do it.  Your code
seems to make sense to me, and I also checked it successfully with some
QuickCheck properties:

 -- check that every "partition" generated by multiPart is in fact a valid
partition.
propMultiPartCorrect :: [Int] -> Bool
propMultiPartCorrect set = all (== sset) (map (sort . concat) $ multiPart
sset)
  where sset = sort set

-- check that multiPart does not generate the same partition twice.
propMultiPartDisjoint :: [Int] -> Bool
propMultiPartDisjoint set = nub parts == parts
  where parts = sort . map sort . multiPart . sort $ set

I didn't write a test to check that multiPart doesn't miss any partitions,
but inspecting some small examples seems to indicate that it doesn't.

It would be nice if one could get rid of the (<=) and hence Ord
> without allowing duplicates. Furthermore, I haven't worried at all
> about space or time efficiency while writing this. I'd want to get it
> right first.


One optimization that might (?) make it faster is to generate subset
complements along with subsets (as I did in my original code), which would
allow getting rid of the \\.  But optimizing certainly isn't my forte.  As
for getting rid of the Ord, I'm going to go out on a limb and conjecture
that the Ord is necessary for an efficient implementation (i.e. with only
Eq, the best you can do is to generate ALL partitions and then eliminate
duplicates).  Off the top of my head I'm not sure how you'd go about trying
to prove it, though.

-Brent
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070724/1b09fd7e/attachment.htm