CLR cover
Previous problem

Problem 117: Online Generation of de Bruijn Words

Next problem

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.