Math.Combinatorics.Multiset

Just a quick note to say that I’ve just uploaded a new package, multiset-comb, to Hackage. It primarily has functions for generating all the distinct permutations and partitions of a multiset (a set where elements are allowed to occur multiple times). Efficiently generating distinct permutations and partitions of a multiset is nontrivial (generating all partitions and permutations as if all the elements were distinct, and then discarding duplicate results, is hopelessly inefficient). The permutations code is new; the partitions code is a slight generalization of the code from my article in Issue 8 of the Monad.Reader. I put this code together primarily because I need it for my combinatorial species library (look for a new release of that soon!), but it’s fairly independent, and I thought others might find it useful, so I’m releasing it as a separate library.

About these ads
This entry was posted in haskell, projects and tagged , , , , . Bookmark the permalink.

4 Responses to Math.Combinatorics.Multiset

    • Brent says:

      Thanks for pointing those out, I was unaware that someone had published Haskell versions of Knuth’s algorithms. However, there are several important ways in which my code is more general, and not just reinventing the wheel: (1) my code doesn’t require Eq and Ord instances; (2) my partition algorithm actually returns a list of multisets of multisets, not just a list of list of lists, so more information is retained about which parts are equal to each other (otherwise to recover this information you’d have to do a lot of post-facto equality tests), and (3) my solutions are purely functional algorithms derived from first principles, rather than (inefficient) transliterations of imperative algorithms into a functional language, so I expect (although I haven’t done any benchmarking yet) that my code is more efficient. Anyway, I am in no way knocking the great work of Knuth or Balazs Komuves (who wrote the combinat package) but I do think my code has some additional things to offer!

      • xyz says:

        (1) the Eq/Ord instances are only used in a trivial way (the input format is different, as you note), and you don’t have the notion of “multiset” without Eq anyway. Also I think that in any realistic use case you already have Eq/Ord.

        (2) you may have some point here, though it seems to me that the differences are trivial (use `map head . group’ and so on). Also, since my code builds on vector partitions exactly the same way, all it would take to have the same functionality is an email and half an hour free time. The code actually contains the expression `concat (zipWith replicate ns zs)’, so you could even say it is a feature!

        (3) those “inefficient transliterations” are 3-10x faster according to my quick benchmarks (which consisted of computing the lengths of the resulting lists of permutations/partitions for some random examples, which took between 1 and 200 secs to compute).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s