Hi all,<br><br>I've written some code to generate set partitions:<br><br>import Control.Arrow<br>import Data.List<br><br>-- pSet' S generates the power set of S, with each subset paired<br>-- with its complement.
<br>-- e.g. pSet' [1,2] = [([1,2],[]),([1],[2]),([2],[1]),([],[1,2])].<br>pSet' :: [a] -> [([a],[a])]<br>pSet' [] = [([],[])]<br>pSet' (x:xs) = mp first ++ mp second where<br> mp which = map (which (x:)) psRest
<br> psRest = pSet' xs<br><br>-- partitions S generates a list of partitions of S. <br>-- e.g. partitions [1,2,3] = [[[1,2,3]],[[1,2],[3]],[[1,3],[2]],[[1],[2,3]],[[1],[2],[3]]].<br>partitions :: [a] -> [[[a]]]<br>
partitions [] = [[]]<br>partitions (x:xs) = (pSet' xs) >>= ((x:) *** partitions >>> uncurry (map . (:)))<br><br>However, this version of partitions generates duplicates when given a multiset, for example:
<br><br>*Combinatorics> partitions [1,1,2]<br>[[[1,1,2]],[[1,1],[2]],[[1,2],[1]],[[1],[1,2]],[[1],[1],[2]]]<br><br>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?
<br><br>-Brent<br><br>PS Yes, this is for Project Euler. =)<br>