Constructing de Bruijn sequences with co-lexicographic order: The k-ary Grandmama sequence. (August 2018)

• Record Type: Journal Article
• Authors: Dragon, Patrick Baxter; Hernandez, Oscar I.; Sawada, Joe; Williams, Aaron; Wong, Dennis
• Is Part Of: European journal of combinatorics. Volume 72(2018)
• Page Start: 1
• Page End: 11
• Publication Date: 2018-08
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2018.03.006
• Languages: English
• ISSNs: 0195-6698

Abstract

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.