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.

Experiment

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

1. Set Order n to 3 and Rotation shift to 0. Observe the cyclic sequence 00011101.
2. 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.
3. 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.