# Problem 117: Online Generation of de Bruijn Words

A binary de Bruijn word of order $n$ is a word of length $2^n$ on the alphabet $\{\sa{0},\sa{1}\}$ in which all binary words of length $n$ occur cyclically exactly once.

A de Bruijn word can be generated by starting from a binary word of length $n$ and then repeating the operation $\NEXT(w)$ below. The operation computes the next bit of the sought de Bruijn word and updates the word $w$. The whole process stops when $w$ returns to its initial word.

deBruijn$(n \textrm{ positive integer})$
    \begin{algorithmic}
\STATE $(x,w_0)\leftarrow (\varepsilon,\mbox{a binary word of length }n)$
\STATE $w\leftarrow w_0$
\REPEAT
\STATE $w\leftarrow$ Next$(w)$
\STATE $x\leftarrow x\cdot w[n-1]$
\UNTIL{$w = w_0$}
\RETURN{$x$}
\end{algorithmic}


The operation $\NEXT$ needs only to be specified to get an appropriate online generation algorithm. Let $\overline{b}$ denote the negation of the bit $b$.

Next$(w \textrm{ non-empty word of length } n)$
    \begin{algorithmic}
\IF{$w[1..n-1]\cdot\mathtt{1} \mbox{ smallest in its conjugacy class}$}
\STATE $b\leftarrow \overline{w[0]}$
\ELSE
\STATE $b\leftarrow w[0]$
\ENDIF
\RETURN{$w[1..n-1]\cdot b$}
\end{algorithmic}


Show that the execution of deBruijn$(n)$ generates a binary de Bruijn word of length $2^n$.

## References

• J. Sawada, A. Williams, and D. Wong. A surprisingly simple de Bruijn sequence construction. Discrete Mathematics, 339(1):127-131, 2016.