De Bruijn Prefer-One Cycle

A De Bruijn sequence of order n on an alphabet of size k is a cyclic sequence in which every possible length-n string occurs exactly once as a contiguous substring. For binary alphabets (k=2), the sequence has length 2ⁿ. The prefer-one algorithm is a simple greedy method to generate a specific universal cycle: start with n zeros, and repeatedly append a 1 if it creates a previously unseen length-n suffix; otherwise, append a 0.

Worked Example

Let's generate the binary De Bruijn sequence for n=3 using the prefer-one strategy.

Start with the sequence 000. Seen set: {000}.
Current suffix is 00. Appending 1 gives 001. Not seen, so append 1. Sequence: 0001. Seen: {000, 001}.
Current suffix is 01. Appending 1 gives 011. Not seen, so append 1. Sequence: 00011. Seen: {000, 001, 011}.
Current suffix is 11. Appending 1 gives 111. Not seen, so append 1. Sequence: 000111. Seen: {000, 001, 011, 111}.
Current suffix is 11. Appending 1 gives 111. Already seen! So append 0 instead. Sequence: 0001110. Seen: {000, 001, 011, 111, 110}.
Current suffix is 10. Appending 1 gives 101. Not seen, so append 1. Sequence: 00011101. Seen: {000, 001, 011, 111, 110, 101}.
At length 8, all 2³ = 8 cyclic length-3 words have been covered once (with wrap-around suffixes 010 and 100), so the cycle terminates at 00011101.

The cyclic sequence is 00011101. If we wrap around, the length-3 substrings are: 000, 001, 011, 111, 110, 101, 010, 100. This covers all 8 possible binary words exactly once.

Experiment

Use the interactive module to explore De Bruijn sequences for different values of n.

Set Order n to 3 and Rotation shift to 0. Observe the cyclic sequence 00011101.
Change the Rotation shift to 2. Notice that the cyclic sequence shifts by 2 positions to become 01110100, but it still represents the same cycle and covers the same set of words.
Set Order n to 4. See how the sequence length increases to 16, and the linear cover length becomes 19 to include the necessary wrap-around padding.

Limitations

The greedy prefer-one strategy is specific to binary alphabets and produces one specific De Bruijn sequence (the lexicographically largest one, if we reverse the roles of 0 and 1). There are many other De Bruijn sequences for a given n, which can be found by finding Eulerian cycles in the De Bruijn graph. The interactive module computes the sequence by simulating the greedy algorithm, which takes exponential time O(2ⁿ) and is therefore limited to small values of n.

References

The generation of De Bruijn sequences using greedy approaches is a well-studied topic in combinatorics.

De Bruijn Prefer-One Cycle