Tagged: de Bruijn Sequence

Complete Word Tours

Suppose we were to take a finite alphabet \mathbb{A}_n of n letters, say \{ 0, 1, \ldots, n-1\}, and we considered all the possible ‘words’ of a given length. For instance, the worlds of length 2 are:

\{00, 01, \ldots, 0(n-1), 10, 11, \ldots, (n-1)(n-1)\}

and there are n^2 many of these. Let’s denote the set of length-m words using the alphabet \mathbb{A}_n by \mathbb{W}^m_n.

What I am interested in now is “For a given n and m, what is the minimum length string of letters I can write down and still be sure that every word in \mathbb{W}^m_n appears somewhere in it as a substring?”. Why might I be interested in such a thing? Because I really should be working on my PhD, that’s why.



contains every length-2 word of 2 letters, in order 01, 11, 10, 00. It’s of optimal length, too, because if we start with just ’01’ and successively add ‘1’, ‘0’, and ‘0’, we find that at every stage the newly added letter creates a new sub-word not previously seen, and so every element of \mathbb{W}^2_2 appears exactly once. We cannot delete a letter to make a shorter string without losing one of the words. Similarly,




are examples of optimal tours through \mathbb{W}^3_2 and \mathbb{W}^2_3 respectively, as they both have this property that each letter added after the first m adds a previously unseen word.

Notice I’ve introduced the terminology tour for any string \tau that contains all words in a given \mathbb{W}^m_n, with optimal tour being the tour \tau^m_n that is of minimum possible length for that m and n.

Continue reading