A surprisingly simple de Bruijn sequence construction

Joe Sawada, Aaron Williams, Dennis Wong

Research output: Contribution to journalArticlepeer-review

36 Citations (Scopus)


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

Original languageEnglish
Pages (from-to)127-131
Number of pages5
JournalDiscrete Mathematics
Issue number1
Publication statusPublished - 6 Jan 2016
Externally publishedYes


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


Dive into the research topics of 'A surprisingly simple de Bruijn sequence construction'. Together they form a unique fingerprint.

Cite this