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.

@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}
}