Efficient constructions of the Prefer-same and Prefer-opposite de Bruijn sequences

The greedy Prefer-same de Bruijn sequence construction was first presented by Eldert, Gray, Gurk, and Rubinoff in 1958. As a greedy algorithm, it has one major downside: it requires an exponential amount of space to store the length \(2ⁿ\) de Bruijn sequence. Though de Bruijn sequences have been heavily studied over the last 60 years, finding an efficient construction for the Prefer-same de Bruijn sequence has remained a tantalizing open problem. In this article, we unveil the underlying structure of the Prefer-same de Bruijn sequence and solve the open problem by presenting an efficient algorithm to construct it using \(O(n)\) time per bit and only \(O(n)\) space. Following a similar approach, we also present an efficient algorithm to construct the Prefer-opposite de Bruijn sequence.