Generating fixed density bracelets of arbitrary base

Abstract

Bracelets are lexicographically minimal k-ary strings symmetric under rotation and reversal. In this paper, we present an algorithm for lexicographic listing of bracelets with fixed density. Our algorithm works for arbitrarily large alphabet size and each successive bracelet is generated in constant amortized time.

Keywords:

• bracelet with fixed density
• necklace
• CAT algorithm
• combinatorial generation

2010 AMS Subject Classifications:

• 05-04
• 68R05
• 68R15

Acknowledgements

This work was partially supported by FAST-NU under the grant 11L-270/NU-R/11. The authors thank Joe Sawada for all the useful discussions and the valuable comments.