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`

.

##
About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

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. :)

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

The package containing the code is freely available here: http://hackage.haskell.org/package/multiset%2Dcomb In particular you can see the implementation of Sawada’s algorithm here: http://hackage.haskell.org/packages/archive/multiset-comb/0.2.2/doc/html/src/Math-Combinatorics-Multiset.html#cycles

Thanks!!

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