# A surprisingly simple de Bruijn sequence construction

• Published in 2016
In the collections
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.

### 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,Combinatorics}
}