Generate de Bruijn sequences

A de Bruijn sequence, named after the Dutch mathematician Nicolaas Govert de Bruijn [dB46], is a cyclic sequence of length $k^n$ in which every string of length $n$ over the alphabet $\{0,1,\ldots,k-1\}$ appears exactly once as a substring. For instance, 00010111 is a binary de Bruijn sequence for strings of length $n=3$, as it contains each of the strings 000,001,010,011,100,101,110,111 starting at positions 1,2,3,5,8,4,7,6, respectively (the string wraps around cyclically at the end).

The first seven algorithms running on this website are successor rules that determine the value of the next bit as a function of the values of the preceding $n$ bits. The first four rules are based on the pure cycling register (PCR), and the next three rules are based on the complementary cycling register (CCR). The last four algorithms are greedy algorithms that determine the next symbol greedily according to some rule, so that the next substring of length n has not been encountered before. The four greedy rules are

• Prefer largest: take the largest possible symbol
• Prefer smallest: take the smallest possible symbol
• Prefer opposite: increment last symbol by $\geq 1$ as little as possible
• Prefer same: increment last symbol by $\geq 0$ as little as possible

All those algorithms are described in the paper by Gabric, Sawada, Williams and Wong [GSWW18].

For a more in-depth treatment of de Bruijn sequence constructions see the spin-off project debruijnsequence.org.

The number of de Bruijn sequences is $(k!)^{k^{n-1}}/k^n$, which for the binary case $k=2$ is OEIS A016031.

[Zipped C source code (GNU GPL)]

• [dB46] N. G. de Bruijn. A combinatorial problem. Nederl. Akad. Wetensch., Proc., 49:758– 764 = Indagationes Math. 8, 461–467 (1946), 1946.
• [GSWW18] D. Gabric, J. Sawada, A. Williams, and D. Wong. A framework for constructing de Bruijn sequences via simple successor rules. Discrete Math., 341(11):2977–2987, 2018.