# Finite universal numbers

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:

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?

• They are called De Bruijn sequences. That page lists some construction methods. Oct 13 '17 at 13:45
• For binary, the Gray code is a simple way to find one. Later the article shows how to construct one for ternary. Oct 13 '17 at 13:46
• @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. Oct 13 '17 at 13:50