Given an alphabel $\Sigma$, a sequence $\bar{s}$ in $\Sigma^*$ is said to be k-universal if it contains all sub-sequences of $\Sigma^k$. I am interested by the smallest of these k-universal sequences. Of course, it should have length at least $|\Sigma|^k + k - 1$. Empirically, there are a lot of k-universal sequences of this length.

For example, for $\Sigma = \{0, 1\}$ and $k = 3$, a few of these sequences are 0001011100, 0001110100 and 0010111000. Each of them has a length of $10 = 2^3 + 3 - 1$ and contains all the sub-sequences 000, 001, 010, 011, 100, 101, 110 and 111.

Is there a fast way to find smallest k-universal sequences, even just one?

What I've tried

Looking for such sequences with a binary alphabet $\Sigma = \{0, 1\}$, I found out that we could model this problem as finding an Hamiltonian path (going through all vertices) on an oriented graph G(V, E), where the vertices V are the sequences of $\Sigma^k$ and for each $x,y \in \Sigma, \bar{s} \in \Sigma^{k-1}$, there is an edge $(x\bar{s}) \to (\bar{s}y) \in$ E. For $k = 1, 2, 3, 4$, I rendered manually the graphs below:

Graph for k=1

Graph for k=2

Graph for k=3

Graph for k=4

However, computing an Hamiltonian path is an NP-complete problem in general, and after implementing it this solution does not scale. Is there a more generative way to obtain the smallest k-universal numbers, e.g. with grammars?

  • 2
    $\begingroup$ They are called De Bruijn sequences. That page lists some construction methods. $\endgroup$ Oct 13 '17 at 13:45
  • $\begingroup$ For binary, the Gray code is a simple way to find one. Later the article shows how to construct one for ternary. $\endgroup$ Oct 13 '17 at 13:46
  • $\begingroup$ @RossMillikan Gray codes are not what I want. They transform numbers by exactly one digit anywhere in the number, whereas I shift the digits and insert a new one. JaapSherphuis This is exactly what I wanted. $\endgroup$ Oct 13 '17 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.