A surprisingly simple de Bruijn sequence construction

• Published in 2016
• Added on 2018-06-25

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

• https://www.sciencedirect.com/science/article/pii/S0012365X15002873

Other information

BibTeX entry

@article{AsurprisinglysimpledeBruijnsequenceconstruction,
	key = {AsurprisinglysimpledeBruijnsequenceconstruction},
	type = {article},
	title = {A surprisingly simple de Bruijn sequence construction},
	author = {Joe Sawada and Aaron Williams and DennisWong},
	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.},
	comment = {},
	date_added = {2018-06-25},
	date_published = {2016-12-07},
	urls = {https://www.sciencedirect.com/science/article/pii/S0012365X15002873},
	collections = {Basically computer science,Combinatorics},
	url = {https://www.sciencedirect.com/science/article/pii/S0012365X15002873},
	year = 2016,
	urldate = {2018-06-25}
}