A simple shift rule for [formula omitted]-ary de Bruijn sequences.

A k -ary de Bruijn sequence of order n is a cyclic sequence of length k n in which each k -ary string of length n appears exactly once as a substring. A shift rule for a de Bruijn sequence of order n is a function that maps each length n substring to the next length n substring in the sequence. We present the first known shift rule for k -ary de Bruijn sequences that runs in O ( 1 ) -amortized time per symbol using O ( n ) space. Our rule generalizes the authors’ recent shift rule for the binary case (A surprisingly simple de Bruijn sequence construction, Discrete Math. 339, 127–131). [ABSTRACT FROM AUTHOR]