Math.Combinatorics.Multiset

Posted on February 20, 2010 by Brent

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 algorithm, combinatorial, multiset, partitions, permutations. Bookmark the permalink.

4 Responses to Math.Combinatorics.Multiset

xyz says:

February 21, 2010 at 6:12 am

It seems that you are “reinventing the wheel”:

http://hackage.haskell.org/packages/archive/combinat/0.2.4/doc/html/Math-Combinat-Permutations.html#6

http://hackage.haskell.org/packages/archive/combinat/0.2.4/doc/html/Math-Combinat-Partitions.html#3

Reply
- Brent says:
  
  February 21, 2010 at 12:40 pm
  
  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!
  
  Reply
  - xyz says:
    
    February 21, 2010 at 2:13 pm
    
    (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).
    
    Reply
    - Paul Delhanty says:
      
      March 13, 2010 at 11:30 pm
      
      @xyz – as I understand it, hackage is not supposed to be a monoculture. Just because you were first with a multiset implementation does not preclude others from publishing multiset implementations. Free competition stimulates innovation – see Jeff Attwood’s post on reiventing the wheel here:
      
      http://www.codinghorror.com/blog/2009/02/dont-reinvent-the-wheel-unless-you-plan-on-learning-more-about-wheels.html
      
      Also, you would have been more honest if you had identified yourself clearly in your first post as the author of the competing package.
      
      Reply