My question is most precisely stated in the title. As an example, if we consider base 10, and k=4, then I am asking, is it possible to have a sequence of length 10^4 + 3, such that each 4 digit number appear exactly once in a consecutive block? This is related to finding a Hamiltonian cycle in a b-regular graph. But one would also like to construct the actual cycle.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Google for "generating De Bruijn sequences".
answered Oct 16, 2010 at 19:23
-
$\begingroup$ Would this be the shortest correct answer to a mathoverflow question? $\endgroup$ Commented Oct 16, 2010 at 19:40
-
$\begingroup$ Sorry Mariano. But I couldn't find an algorithm for generating De Bruijn sequence with base other than 2, and even the one for base 2 seems very complicated. Do you have any quick insight on that? $\endgroup$ Commented Oct 18, 2010 at 17:21