Constructing de Bruijn sequences with co-lexicographic order: The k-ary Grandmama sequence. (August 2018) - Dragon, Patrick Baxter; Hernandez, Oscar I.; Sawada, Joe; Williams, Aaron; Wong, Dennis
Abstract: A k -ary de Bruijn sequence of order n is a circular k -ary string of length k n which contains every k -ary string of length n exactly once as a substring. It is well-known that a k -ary de Bruijn sequence of order n can be constructed by concatenating the aperiodic prefixes of the k -ary necklaces of length 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 ) -time.