Math.Combinatorics.Multiset and Sawada’s algorithm

I’ve uploaded a new version of my Math.Combinatorics.Multiset library (see the previous announcement here). I’ve added a few more fairly simple algorithms (splitting a multiset into two pieces in all possible ways; finding all size-k submultisets of a multiset), and one which is decidedly NOT simple. I wanted to generate all distinct cyclic arrangements of the elements from a multiset — in other words, sequences which are distinct up to cyclic rotations. For example, the multiset \{1,1,2,2,3\} has six distinct cyclic arrangements:

\langle 11223\rangle, \langle 11232\rangle, \langle 11322\rangle, \langle 12123\rangle, \langle 12132\rangle, \langle 12213\rangle

How to generate all such cyclic arrangements (also called “necklaces”), given a multiset? I thought about it for a whole day and decided that it was rather difficult! (If you don’t believe me, try coding it yourself.) A bit of searching confirmed my suspicion but turned up a nice 2003 paper by Joe Sawada with a fast algorithm (which I still don’t quite understand — it depends on some non-trivial properties of necklaces!). So, I implemented it, as Math.Combinatorics.Multiset.cycles.

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

4 Responses to Math.Combinatorics.Multiset and Sawada’s algorithm

  1. lpsmith says:

    I’ve spent some time trying to understand the efficient algorithms to generate necklaces, although limited to sets, not multisets. I am very interested in hearing any explanations of the algorithm that you come up with. :)

  2. There is some interesting stuff in the paper you’ve shared. is it possible to see your implementation?

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