On 7/24/07, Brent Yorgey
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