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.

Associate 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.

### 5 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?

3. Anonymous says:

Hello, can you implement this multiset permutation code as a standalone or into one of these free online haskell editors? Thank you.

This site uses Akismet to reduce spam. Learn how your comment data is processed.