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 has six distinct cyclic arrangements:

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.