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

作者：Sawada J^*; Williams A

来源：Theoretical Computer Science, 2013, 502: 46-54.

DOI：10.1016/j.tcs.2012.01.013

• Lyndon word
• Necklace
• Pseudo-necklace
• Gray code
• Cool-lex
• Fixed-density
• de Bruijn sequence

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.

• 出版日期2013-9-2