Generate all de Bruijn sequences

Question

There are several methods to generate a de Bruijn sequence. Is there a general algorithm to create all unique (rotations are counted as the same) De Bruijn sequences for a binary alphabet of length $n$, or $B(2, n)$?

For example, one such sequence for $B(2, 5)$ is $00000111011010111110011000101001$.

Answer 1

For small $n$, a depth-first search using a list or set of "already seen" subsequences does the trick.

Edit: Here is the code I wrote in 2015-2016 (I would write it differently now). It included one of my "clever tricks" where since the lexicographically first string of a particular cyclic sequence starts with $n$ zeros, if there are equal counts of zeros and ones, then all substrings (including the wraparound ones) are included, obviating the need for string rotations.

# De Bruijn sequences return...
# Generate strings using DFS, ignoring strings with "seen" subsequences

def S(arrange, seen, N):
    # len(arrange) can be removed if 00000 is marked as seen
    if len(arrange) == 2**N and 2*arrange.count(0) == 2**N:
        print(''.join(map(str, arrange)))

    for c in (0, 1):
        new_seen = seen[:]
        new_arrange = arrange + [c]

        word = ''.join(map(str, new_arrange[-N:]))
        seen_i = int(word, 2)

        if not new_seen[seen_i]:
            new_seen[seen_i] = 1
            S(new_arrange, new_seen, N)


S([0]*5, [0]*2**5, 5)  # Beginning must be 00000

Answer 2

Yes. The approach which finds an Eulerian cycle of an $(n-1)$-dimensional graph is easily adapted to find all Eulerian cycles starting at a given vertex. Since rotating a sequence corresponds to tracing the same Eulerian cycle but starting at a different vertex, this adaptation generates exactly one representative for each equivalence class of sequences. In fact, you can even easily make it enumerate them in lexicographic order.

Answer 3

Enumerating Eulerian cycles is the way to go. This answer gives an algorithm in $\mathcal{O}(P(E)N)$ where $P$ is polynomial and $N$ is the number of Eulerian cycles.

Here is a more efficient algorithm : Choose a vertex $v$ and enumerate all directed spanning trees (with edges pointing toward the root) rooted at $v$ (It can be done in $\mathcal{O}(V + E + NE) = \mathcal{O}(NV)$ where $N$ is the number of rooted spanning tree) because $E = \mathcal{O}(V)$ for de Bruijn graphs). Find a cycle through the graph by starting at $v$. At each vertex you cross, choose some leaving edge you never took, and never take the edge going back to its parent on the tree before taking every other edge leaving this vertex. Enumerate all the cycles you find like this by taking all the possible choices at every vertex. This can be done in $\mathcal{O}(NV)$, where $N$ is the number of Eulerian cycles.

At the end, you should find every possible Eulerian cycle in an optimal time.

Take all cyclic permutations of all Eulerian cycle to get all the de Bruijn sequences.

This algorithm is based on the BEST theorem for the enumeration of Eulerian cycles.