A Gray Code for Necklaces of Fixed Density
Terry Min Yih Wang, Carla D. Savage · SIAM Journal on Discrete Mathematics · 1996
A necklace is an equivalence class of binary strings under rotation. In this paper, we present a Gray code listing of all n-bit necklaces with d ones so that (i) each necklace is listed exactly once by a representative from its equivalence class and (ii) successive representatives, including the last and the first in the list, differ only by the transposition of two bits. The total time required is ${\text{O}}(nN(n,d))$, where $N(n,d)$ denotes the number of n-bit binary necklaces with d ones. This is the first algorithm for generating necklaces of fixed density which is known to achieve this time bound.