[Haskell-cafe] Re: partitions of a multiset

[Pekka Karjalainen]

On 7/24/07, Brent Yorgey <byorgey at gmail.com> wrote:
> I'm not sure what a formal
> mathematical definition would be off the top of my head; but in Haskell,
> 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 ]

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.

Pekka