A Fast Algorithm to Enumerate Fixed Density Bracelets
Saira Karim, Zareen Alamgir · 2012
A bracelet is the lexicographically smallest k-ary string equivalent under rotation and reversal. A bracelet is said to be of fixed density, if the number of occurrences of the symbol 0 in the string is fixed. In this work, we present a simple recursive scheme to list bracelets with fixed density d. We claim that our scheme is optimal in terms of time requirements, as it takes constant time on the average to list a binary bracelet with fixed density. We use sophisticated combinatorial techniques to prove our claim.