Hi all,

I've written some code to generate set partitions:

import Control.Arrow
import Data.List

-- pSet' S generates the power set of S, with each subset paired
--   with its complement.
--   e.g. pSet' [1,2] = [([1,2],[]),([1],[2]),([2],[1]),([],[1,2])].
pSet' :: [a]   -> [([a],[a])]
pSet'    []     = [([],[])]
pSet'    (x:xs) = mp first ++ mp second where
    mp which = map (which (x:)) psRest
    psRest = pSet' xs

-- partitions S generates a list of partitions of S.
-- e.g. partitions [1,2,3] = [[[1,2,3]],[[1,2],[3]],[[1,3],[2]],[[1],[2,3]],[[1],[2],[3]]].
partitions :: [a] -> [[[a]]]
partitions [] = [[]]
partitions (x:xs) = (pSet' xs) >>= ((x:) *** partitions >>> uncurry (map . (:)))

However, this version of partitions generates duplicates when given a multiset, for example:

*Combinatorics> partitions [1,1,2]
[[[1,1,2]],[[1,1],[2]],[[1,2],[1]],[[1],[1,2]],[[1],[1],[2]]]

The partition [[1,2],[1]] is generated twice (order doesn't matter). I'd like to write a version of partitions which generates duplicate-free output even for input multisets, but haven't come up with a good method yet. Any ideas?

-Brent

PS Yes, this is for Project Euler. =)