A simple shift rule for k-ary de Bruijn sequences

作者：Sawada Joe^*; Williams Aaron; Wong Dennis

来源：Discrete Mathematics, 2017, 340(3): 524-531.

DOI：10.1016/j.disc.2016.09.008

• k-ary de Bruijn sequence
• De Bruijn sequence
• Universal cycle
• Necklaces
• Shift Gray code
• CAT algorithm
• Generate
• Shift rule
• Successor rule

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). Published by Elsevier B.V.

• 出版日期2017-3