[Haskell-cafe] Re: partitions of a multiset

DavidA polyomino at f2s.com
Mon Jul 23 17:10:47 EDT 2007

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.

More information about the Haskell-Cafe mailing list