4
$\begingroup$

Messing around with numbers has lead me to the following problem, which I am struggling with. (No, not a homework question, just a problem I've thought up myself):

A binary de Bruijn sequence of order $n$ is a circular string of bits that contains every possible bit pattern of size $n$ exactly once each. These sequences have a length of $2^n$.

The smallest $2^{2^{n-1}-n}$ de Bruijn sequences of order $n$ are distinct, and any other $n$th order sequences are rotations of sequences within that set. The number of distinct sequences for orders $1$ through to $7$ are $1, 1, 2, 16, 2048, 67108864$ and $1.44\cdot10^{17}$, respectively.

Eg: for $n=3$, the distinct sequences can be represented by the smallest 2, being 00011101 and 00010111. 11101000 is also a de Bruijn sequence of order 3, but is not distinct from the first two, as it is a rotation of 00011101.

Problem: Create an algorithm to find the $67108864$ smallest de Bruijn sequences of order 6 "efficiently" (no brute force), in "reasonable time" (harder to define: would have to do with the time complexity/Big-O Notation. Obviously quicker is better)

REFERENCES

http://mathworld.wolfram.com/deBruijnSequence.html

http://en.wikipedia.org/wiki/De_Bruijn_sequence

EDIT:

Further research shows this question is the equivalent to finding all distinct Eulerian cycles of a de Bruijn graph, and rotating the solution for each cycle to its smallest binary form. Construction of the graph is simple enough, and Hierholzer's algorithm can be used to find Eulerian cycles. The question remains, how to use Hierholzer's algorithm efficiently to find all distinct Eulerian cycles?

$\endgroup$
1
  • 1
    $\begingroup$ I was messing with this myself aswell. I did not find an algorithm, but I did use a few things to simplify the brute force. Namely inverting the number (1's become 0's and vice versa) and using the reverse order of a sequence will both yield another (or maybe the same) sequence. Half of the bits have to be 1's. The highest value of the binary number representation of the sequence can be obtained with the prefer-one algorithm. The lowest value would be the inverse of that rotated to have $n$ zeros in front. The least significant bit hast to be a 1 so you have to take at least steps of two. $\endgroup$ Apr 22, 2014 at 8:43

1 Answer 1

1
$\begingroup$

Recently reviewed this question again, and have found what might be the right answer at https://chessprogramming.wikispaces.com/De+Bruijn+Sequence+Generator. The remarks given for the program it contains is confusing, and I am yet to test the program and see how/if it works. While it is said to be designed to generate binary De Bruijn sequences, I am not sure if it is/isn't possible to adapt this to generate all distinct binary De Bruijn sequences. Trying to interpret the logic of this program is well above my pay grade!

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .