I wrote about superpermutations here: a superpermutation is a string that has as substrings all the permutations of some set of symbols.

For example, there are six permutations of the symbols 1, 2, 3. They are: 123, 132, 213, 231, 312, 321. The string `123121321`

has all six of these as substrings – and it’s the shortest string that does, with only one three-character substring that isn’t a permutation: the 121 in the middle.

For larger numbers of symbols it’s impossible to do quite so well. For example, there are 24 different permutations of the symbols 1, 2, 3, 4, and the shortest superpermutation is `123412314231243121342132413214321`

, which has 33 characters. So there are 30 different four-character substrings, and six of them contain repeated symbols: `1231`

, `2312`

; `3121`

and `1213`

(which overlap with each other); `2132`

, and `1321`

.

Here it is again, with the non-permutations highlighted:

`1234`

**1231**4**2312**4**31213**4**2132**4**1321**4321

No general formula is known for the length of the shortest superpermutation on n symbols. If we denote this length *s*(*n*), then it is known that for *n* ≥ 3*,*

and it is known that neither bound is tight in general. We know the lower bound is not tight because *s*(5) has been computed exactly and is equal to 153, whereas the formula for the lower bound gives 152. We know the upper bound is not tight because there are superpermutations on 6 symbols of length 872, so we know that *s*(6) ≤ 872, whereas the formula for the upper bound gives 873.