On 7/24/07, Pekka Karjalainen <p3k@iki.fi> wrote:
On 7/24/07, Brent Yorgey <byorgey@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