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.