Interesting Esoterica

A surprisingly simple de Bruijn sequence construction

Article by Joe Sawada and Aaron Williams and DennisWong
  • Published in 2016
  • Added on
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

Other information

key
AsurprisinglysimpledeBruijnsequenceconstruction
type
article
date_added
2018-06-25
date_published
2016-10-09

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-10-09},
	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}
}