Recall from an earlier blog post that the minimal superpermutation problem asks for the shortest string on the symbols “1”, “2”, …, “n” that contains every permutation of those symbols as a contiguous substring. For example, “121” is a minimal superpermutation on the symbols “1” and “2”, since it contains both “12” and “21” as substrings, and there is no shorter string with this property.

Until now, the length of minimal superpermutations has only been known when n ≤ 4: they have length 1, 3, 9, and 33 in these cases, respectively. It has been conjectured that minimal superpermutations have length \(\sum_{k=1}^n k!\) for all n, and I am happy to announce that Ben Chaffin has proved this conjecture when n = 5. More specifically, he showed that minimal superpermutations in the n = 5 case have length 153, and there are exactly 8 such superpermutations (previously, it was only known that minimal superpermutations have either length 152 or 153 in this case, and there are at least 2 superpermutations of length 153).

The Eight Minimal Superpermutations

The eight superpermutations that Ben found are available here (they’re too large to include in the body of this post). Notice that the first superpermutation is the well-known “easy-to-construct” superpermutation described here, and the second superpermutation is the one that was found in [1]. The other six superpermutations are new.

One really interesting thing about the six new superpermutations is that they are the first known minimal superpermutations to break the “gap pattern” that previously-known constructions have. To explain what I mean by this, consider the minimal superpermutation “123121321” on three symbols. We can think about generating this superpermutation greedily: we start with “123”, then we append the character “1” to add the permutation “231” to the string, and then we append the character “2” to add the permutation “312” to the string. But now we are stuck: we have “12312”, and there is no way to append just one character to this string in such a way as to add another permutation to it: we have to append the two characters “13” to get the new permutation “213”.

This phenomenon seemed to be fairly general: in all known small superpermutations on n symbols, there was always a point (approximately halfway through the superpermutation) where n-2 consecutive characters were “wasted”: they did not add any new permutations themselves, but only “prepared” the next symbol to add a new permutation.

However, none of the six new minimal superpermutations have this property: they all never have more than 2 consecutive “wasted” characters, whereas the two previously-known superpermutations each have a run of n-2 = 3 consecutive “wasted” characters. Thus these six new superpermutations are really quite different from any superpermutations that we currently know and love.

How They Were Found

The idea of Ben’s search is to do a depth-first search on the placement of the “wasted” characters (recall that “wasted” characters were defined and discussed in the previous section). Since the shortest known superpermutation on 5 symbols has length 153, and there are 120 permutations of 5 symbols, and the first n-1 = 4 characters of the superpermutation must be wasted, we are left with the problem of trying to place 153 – 120 – 4 = 29 wasted characters. If we can find a superpermutation with only 28 wasted characters (other than the initial 4), then we’ve found a superpermutation of length 152; if we really need all 29 wasted characters, then minimal superpermutations have length 153.

So now we do the depth-first search:

• Find (via brute-force) the maximum number of permutations that we can fit in a string if we are allowed only 1 wasted character: the answer is 10 permutations (for example, the string “123451234152341” does the job).
• Now find the maximum number of permutations that we can fit in a string if we are allowed 2 wasted characters. To speed up the search, once we have found a string that contains some number (call it p) of permutations, we can ignore all other strings that use a wasted character before p-10 permutations, since we know from the previous bullet point that the second wasted character can add at most 10 more permutations, for a total of (p-10)+10 = p permutations.
• We now repeat this process for higher and higher numbers of wasted characters: we find the maximum number of permutations that we can fit in a string with 3 wasted characters, using the results from the previous two bullets to speed up the search by ignoring strings that place 1 or 2 wasted characters too early.
• Etc.

The results of this computation are summarized in the following table:

Wasted characters	Maximum # of permutations
0	5
1	10
2	15
3	20
4	23
5	28
6	33
7	36
8	41
9	46
10	49
11	53
12	58
13	62
14	66
15	70
16	74
17	79
18	83
19	87
20	92
21	96
22	99
23	103
24	107
25	111
26	114
27	116
28	118
29	120

As we can see, it is not possible to place all 120 permutations in a string with 28 or fewer wasted characters, which proves that there is no superpermutation of length 152 in the n = 5 case. C code that computes the values in the above table is available here.

Update [August 18, 2014]: Robin Houston has found a superpermutation on 6 symbols of length 873 (i.e., the conjectured minimal length) with the interesting property that it never has more than one consecutive wasted character! The superpermutation is available here.

IMPORTANT UPDATE [August 22, 2014]: Robin Houston has gone one step further and disproved the minimal superpermutation conjecture for all n ≥ 6. See here.

References

1. N. Johnston. Non-uniqueness of minimal superpermutations. Discrete Mathematics, 313:1553–1557, 2013.