Interesting Esoterica

A surprisingly simple de Bruijn sequence construction

Article by Joe Sawada and Aaron Williams and DennisWong
  • Published in 2016
  • Added on
In the collection
Pick any length \(n\) binary string \(b_1 b_2 \dots b_n\) and remove the first bit \(b_1\). If \(b_2 b_3 \dots 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 \(O(1)\)-amortized time per bit.

Links


BibTeX entry

@article{AsurprisinglysimpledeBruijnsequenceconstruction,
	title = {A surprisingly simple de Bruijn sequence construction},
	abstract = {Pick any length \(n\) binary string \(b{\_}1 b{\_}2 \dots b{\_}n\) and remove the first bit \(b{\_}1\). If \(b{\_}2 b{\_}3 \dots 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 \(O(1)\)-amortized time per bit.},
	url = {https://www.sciencedirect.com/science/article/pii/S0012365X15002873},
	year = 2016,
	author = {Joe Sawada and Aaron Williams and DennisWong},
	comment = {},
	urldate = {2018-06-25},
	collections = {basically-computer-science}
}