On 7/24/07, Brent Yorgey <[EMAIL PROTECTED]> 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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
