# Generate de Bruijn sequences

Generate de Bruijn sequences for strings of length $n$ over the alphabet $\{0,1,\ldots,k-1\}$. The case $k=2$ are bitstrings.
 String length $n$ (max. 15/9/7) Alphabet size $k$ 2 3 4 Algorithm rule Granddaddy (lex. minimal) rule Grandmama rule PCR3 rule PCR4 rule CCR1 rule CCR2 rule CCR3 greedy prefer largest greedy prefer smallest greedy prefer opposite greedy prefer same Output format text file
Output  numbering graphics

## Object info

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.

## Enumeration (OEIS)

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