A Successor Rule Framework for Constructing $k$ -Ary de Bruijn Sequences and Universal Cycles
Daniel Gabrić, Joe Sawada, Aaron Williams, Dennis Wong · IEEE Transactions on Information Theory · 2019
We present a simple framework for constructing$k$-ary de Bruijn sequences, and more generally, universal cycles, via successor rules. The framework is based on the often used method of joining disjoint cycles. It generalizes several previously known de Bruijn sequence constructions based on the pure cycling register and is applied to derive a new construction that is perhaps the simplest of all successors. Furthermore, it generalizes an algorithm to construct binary de Bruijn sequences based on any arbitrary nonsingular feedback function. The framework is applied to derive and prove the correctness of successors to efficiently construct 1) universal cycles for$k$-ary strings of length$n$whose weight is bounded by some$w$and 2) universal cycles for permutations. It has also been subsequently applied to find the first universal cycle constructions for weak orders.