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 nth 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*10^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)
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?