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$
Output format
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

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

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.

Download source code

[Zipped C source code (GNU GPL)]