Hi all,<br><br>I&#39;ve written some code to generate set partitions:<br><br>import Control.Arrow<br>import Data.List<br><br>-- pSet&#39; S generates the power set of S, with each subset paired<br>--&nbsp;&nbsp; with its complement.&nbsp; 
<br>--&nbsp;&nbsp; e.g. pSet&#39; [1,2] = [([1,2],[]),([1],[2]),([2],[1]),([],[1,2])].<br>pSet&#39; :: [a]&nbsp;&nbsp; -&gt; [([a],[a])]<br>pSet&#39;&nbsp;&nbsp;&nbsp; []&nbsp;&nbsp;&nbsp;&nbsp; = [([],[])]<br>pSet&#39;&nbsp;&nbsp;&nbsp; (x:xs) = mp first ++ mp second where<br>&nbsp;&nbsp;&nbsp; mp which = map (which (x:)) psRest
<br>&nbsp;&nbsp;&nbsp; psRest = pSet&#39; 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] -&gt; [[[a]]]<br>
partitions [] = [[]]<br>partitions (x:xs) = (pSet&#39; xs) &gt;&gt;= ((x:) *** partitions &gt;&gt;&gt; uncurry (map . (:)))<br><br>However, this version of partitions generates duplicates when given a multiset, for example:
<br><br>*Combinatorics&gt; 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&#39;t matter).&nbsp; I&#39;d like to write a version of partitions which generates duplicate-free output even for input multisets, but haven&#39;t come up with a good method yet.&nbsp; Any ideas?
<br><br>-Brent<br><br>PS Yes, this is for Project Euler. =)<br>