On 7/23/07, DavidA
Here's the approach I would try. 1. Use Data.List.group to group your multiset, eg [1,1,2] -> [[1,1],[2]] 2. Now apply your partitions function to each of the groups [[1,1],[2]] -> [ [([1,1],[]), ([1],[1]), ([],[1,1])], [([2],[]), ([],[2])] ] (Actually of course, you can probably write a simpler function to do this) 3. Then you just need a function which can list all possible ways of combining the partial partitions (so it's a kind of Cartesian product).
I leave you the pleasure of writing the code.
It seems to me (unless I've missed something?) that this method generates the power set of the original multiset (i.e. all subsets) rather than partitions. (Although, to be sure, it does seem like an elegant and efficient method for doing so; my code for generating the power set of a multiset is somewhat different, I'll have to try this method too.) A partition of a set S is a set of pairwise disjoint subsets of S whose union is S; the definition for a multiset is similar but altered somewhat to allow for the possibility of multiple element copies. 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). I think I've figured out a method of doing this efficiently when trying to list all factorizations of a number (the original application), but it takes advantage of some specific properties of the problem and I'm still interested in a general solution. It would of course be possible to generate all partitions and then use nubBy with suitable list equality (under recursive sorting), but I feel there must be a way to more directly generate unique partitions in the first place. -Brent