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 Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
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: Logo

You are commenting using your 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