Constructing de Bruijn sequences with co-lexicographic order: The k-ary Grandmama sequence

A k k -ary de Bruijn sequence of order n n is a circular k k -ary string of length k n k n which contains every k k -ary string of length n n exactly once as a substring. It is well-known that a k k -ary de Bruijn sequence of order n n can be constructed by concatenating the aperiodic prefixes of the k k -ary necklaces of length n n in lexicographic order. In this article we prove that an alternate de Bruijn sequence is created by replacing lexicographic order with co-lexicographic order. We also provide a simple successor rule for generating each successive symbol in O(n) O ( n ) -time.