This program implements Duval's algorithm to generate binary de Bruijn sequences. The algorithm always returns the lexicographically smallest (first in the alphabet) sequence of a given order. We print the result to stdout in human-readable form, using one byte per digit.
A major advantage of Duval's algorithm is that it runs in amortized O(1) time per bit and requires only O(n) memory. For almost all use cases, n will be less than 40, so the memory usage is negligible. This implementation also runs about 20-40% faster than my prefer-one implementation for medium-sized inputs (20 <= n <= 24).
To compile, just run make. To clean up the directory, use make clean.
To generate the order-n sequence, run ./duval n (Linux) or duval.exe n (Windows). The value of n can be any positive int.
For example, to generate the order-8 sequence and pipe the result to output.txt, run ./duval 8 > output.txt (Linux) or duval.exe 8 > output.txt (Windows).
Shown below are the order-n sequences generated by the program, for n <= 6:
n=1: 01
n=2: 0011
n=3: 00010111
n=4: 0000100110101111
n=5: 00000100011001010011101011011111
n=6: 0000001000011000101000111001001011001101001111010101110110111111
- A description (in French) of the algorithm can be found in the original paper by Jean-Pierre Duval, "Génération d'une section des classes de conjugaison et arbre des mots de Lyndon de longueur bornée."