[Haskell-cafe] Re: partitions of a multiset

Brent Yorgey byorgey at gmail.com
Tue Jul 24 12:39:30 EDT 2007


On 7/23/07, DavidA <polyomino at f2s.com> wrote:
>
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070724/9b7789f1/attachment.htm


More information about the Haskell-Cafe mailing list