You might wonder "what is this image below?". I will tell you in the end, because it is least relevant to the whole thing. But as you reading through try to guess.

Browsing the Robin Houston's blog I happened upon an interesting open problem of superpermutations. Imagine you have $n$ different symbols. What is the shortest string that contains every possible permutation of the symbols? For the $n \le 4$ we have the following results - and each string is a unique solution:

$$ \begin{array}{|l|l|l|} \hline \text{n} & \text{Minimal Superpermutation} & \text{Length} \ \hline 1 & 1 & 1 \ \hline 2 & 121 & 3 \ \hline 3 & 123121321 & 9 \ \hline 4 & 123412314231243121342132413214321 & 33 \ \hline \end{array} $$

They all are palindromes:

(# === StringReverse[#]) & /@ {"123121321",  "123412314231243121342132413214321"}

{True, True}

Here are 8 Minimal Superpermutations for $n=5$. They are very long and only the 1st is a palindrome:

(# === StringReverse[#])&/@{
"123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321",
"123451234152341253412354123145231425314235142315423124531243512431524312543121354213524135214352134521325413251432513425132451321543215342153241532145321",
"123451234152341253412354123145231425314235142315421352413521435213452135421534215432154231245321453241532451325413251432513425132453124351243152431254312",
"123451234152341253412354123145213425134215342135421345214352145321452314253142351423154231245312435124315243125432154325143254132451324153241352413254312",
"123451234152341253412354132541352413542134521342513421534213541231452314253142351423154231245321435214325143215432145324153245132453124351243152431254312",
"123451234152341253412354132514325134251324513254135241354213541231452134521435214532154321534215324153214523142531423514231542312453124351243152431254312",
"123451324513425134521354213524135214352134512341523412534123541231452314253142351423154231245312435124315243125432153421532415321453215432514325413254312",
"123451324153241352413254132451342513452134512341523412534123541231452314253142351423154213542153421543214532143521432514321542312453124351243152431254312"
}

{True, False, False, False, False, False, False, False}

Robin Houston's blog found an excellent short solution for $n=6$ with length 872, which, if I understand correctly, is not yet proven to be minimal. Robin thus disproved the conjecture that for all $n$ minimal superpermutations have length

$$\sum _{k=1}^n k!$$

which in $n=6$ case would give 873. The solution was found by encoding the problem as an instance of the (asymmetric) Traveling Salesman Problem (TSP).

My questions are (warning, I am not a mathematician ;-) ):

• What is Wolfram Language code that finds Minimal Superpermutations?
• Can we use Wolfram Language TSP?
• Can the search be parallelized somehow?
• Can we find anything interesting using computations, basically doing experimental mathematics?

Useful references:

• The Minimal Superpermutation Problem
• Blog: Tackling the Minimal Superpermutation Problem
• Arxiv: Tackling the Minimal Superpermutation Problem
• All Minimal Superpermutations on Five Symbols Have Been Found

So and finally, as promised, the top image comes from turning all 8 solutions of $n=6$ problem into sequence of digits and plotting them. If we denote the list of 8 solutions given above as n6sol, the code is:

ListLinePlot[Range[0, 28, 4] + ToExpression@Characters[n6sol], 
 AspectRatio -> 1/5, ImageSize -> 900, InterpolationOrder -> 2, 
 Axes -> False, Filling -> Table[n -> {n - 1}, {n, 2, 9}]]