A surprisingly simple de Bruijn sequence construction

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

来源：Discrete Mathematics, 2016, 339(1): 127-131.

DOI：10.1016/j.disc.2015.08.002

• De Bruijn sequence
• Universal cycle
• Necklaces
• Shift Gray code
• CAT algorithm
• Generate
• Shift rule
• Successor rule

Pick any length n binary string b(1)b(2)...b(n) and remove the first bit b(1). If b(2)b(3)...b(n)1 is a necklace, then append the complement of b(1) to the end of the remaining string; otherwise append b(1). By repeating this process, eventually all 2(n) binary strings will be visited cyclically. This shift rule leads to a new de Bruijn sequence construction that can be generated in 0(1)-amortized time per bit.

• 出版日期2016-1-6