Example
\(
\def\sa#1{\tt{#1}}
\def\dd{\dot{}\dot{}}
\newcommand{\NEXT}{Next}
\)
$\sa{00010111}$ and $\sa{01000111}$ are
(non-conjugate) de Bruijn words of order $3$.
Let $n=3$ and $w_0=\sa{111}$.
The values of $w$ at line 4 of Algorithm deBruijn are:
$\sa{11}\underline{\sa{0}}, \sa{10}\underline{\sa{1}},
\sa{01}\underline{\sa{0}}, \sa{10}\underline{\sa{0}},
\sa{00}\underline{\sa{0}}, \sa{00}\underline{\sa{1}},
\sa{01}\underline{\sa{1}}, \sa{11}\underline{\sa{1}}.$
Underlined bits form the de Bruijn word $\sa{01000111}$.
For $n=5$ and $w_0=\sa{11111}$ the consecutive values of $w$ are
$\sa{1111}\underline{\sa{0}}$, $\sa{1110}\underline{\sa{1}}$,
$\sa{1101}\underline{\sa{1}}$, $\sa{1011}\underline{\sa{1}}$,
$\sa{0111}\underline{\sa{0}}$, $\sa{1110}\underline{\sa{0}}$,
$\sa{1100}\underline{\sa{1}}$, $\sa{1001}\underline{\sa{1}}$,
$\sa{0011}\underline{\sa{0}}$, $\sa{0110}\underline{\sa{0}}$,
$\sa{1100}\underline{\sa{0}}$, $\sa{1000}\underline{\sa{1}}$,
$\sa{0001}\underline{\sa{0}}$, $\sa{0010}\underline{\sa{1}}$,
$\sa{0101}\underline{\sa{1}}$, $\sa{1011}\underline{\sa{0}}$,
$\sa{0110}\underline{\sa{1}}$, $\sa{1101}\underline{\sa{0}}$,
$\sa{1010}\underline{\sa{1}}$, $\sa{0101}\underline{\sa{0}}$,
$\sa{1010}\underline{\sa{0}}$, $\sa{0100}\underline{\sa{1}}$,
$\sa{1001}\underline{\sa{0}}$, $\sa{0010}\underline{\sa{0}}$,
$\sa{0100}\underline{\sa{0}}$, $\sa{1000}\underline{\sa{0}}$,
$\sa{0000}\underline{\sa{0}}$, $\sa{0000}\underline{\sa{1}}$,
$\sa{0001}\underline{\sa{1}}$, $\sa{0011}\underline{\sa{1}}$,
$\sa{0111}\underline{\sa{1}}$, $\sa{1111}\underline{\sa{1}},$ generating the
de Bruijn word
$$\sa{01110011000101101010010000011111}.$$
|
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.
