Abstract
A k-ary de Bruijn sequence of order n is a circular k-ary string of length kn 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.
Original language | English |
---|---|
Pages (from-to) | 1-11 |
Number of pages | 11 |
Journal | European Journal of Combinatorics |
Volume | 72 |
DOIs | |
Publication status | Published - Aug 2018 |
Externally published | Yes |