Necklaces and Lyndon words in colexicographic and binary reflected Gray code order.

We present the first efficient algorithm to list necklaces, Lyndon words, or pseudo-necklaces of length n in colexicographic order. The algorithm has two interesting properties. First, it can be applied to construct a de Bruijn sequence of order n in O ( 1 ) -time per bit. Second, it can easily be modified to efficiently list necklaces, Lyndon words, or pseudo-necklaces of length n in binary reflected Gray code order. [ABSTRACT FROM AUTHOR]