A Gray code for fixed-density necklaces and Lyndon words in constant amortized time

This paper develops a constant amortized time algorithm to produce a cyclic cool-lex Gray code for fixed-density binary necklaces, Lyndon words, and pseudo-necklaces. It is the first Gray code for these objects that achieves this time bound. The algorithm is applied: (i) to develop a constant amortized time cyclic Gray code for necklaces, Lyndon words, and pseudo-necklaces ordered by density and (ii) to obtain a fixed-density de Bruijn sequence using constant time per n bits on average. In addition to Gray code order, the algorithms can be easily modified to output the strings in co-lex order. (C) 2012 Elsevier B.V. All rights reserved.