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:
123412314231243121342132413214321
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.