Generating a random or arbitrary de Bruijn sequence?

Question

As near as I can tell, there are several methods for generating a single valid de Bruijn sequence using a given deterministic approach, as well as algorithms for churning out all possible sequences. For my purposes, I need only be able to generate random ones.

Ideal would be an algorithm where you can provide part of the sequence, and it will generate the rest of a valid sequence starting with that. But nearly as good would be any technique where I could provide a random seed or something equivalent and be likely to get a new distinct sequence each time I use it.

I'd like to be able to do this for, say, sequences of order-7 and higher, which is why any approach that requires iterating through all possible sequences up front is not feasible, unless it's computationally cheap to generate each next sequence and doesn't need to be done as a batch. If anybody can give me a helpful suggestion or useful link, I'll consider this answered.

Answer 1

If algebraic techniques are used this becomes more feasible.

The paper On Binary de Bruijn Sequences from LFSRs with Arbitrary Characteristic Polynomials by Z. Chang et al available at https://arxiv.org/pdf/1611.10088.pdf provides a solution which the authors state is practical for span $n$ up to about $n=20.$

We propose a construction of de Bruijn sequences by the cycle joining method from linear feedback shift registers (LFSRs) with arbitrary characteristic polynomial f(x). We study in detail the cycle structure of the set $\Omega(f(x))$ that contains all sequences produced by a specific LFSR on distinct inputs and provide a fast way to find a state of each cycle. This leads to an efficient algorithm to find all conjugate pairs between any two cycles, yielding the adjacency graph. The approach is practical to generate a large class of de Bruijn sequences up to order $n \approx 20.$

They also give a link to an implementation.

Focusing on Table 3, their method seems to generate approximately $2^{33}$ de Bruijn sequences of span $7$, $2^{398}$ de Bruijn sequences of span $12$, and $2^{1365}$ de Bruijn sequences of span $20$. This is of course a tiny fraction of the total number of sequences, but quite an impressive number nonetheless.