Code & exploration of Minimal Superpermutation problem

Questions
,
1

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.

sdfa34qersre53qtgreasvx.png
sdfa34qersre53qtgreasvx.png900×181 84.7 KB

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 :wink: ):

  • 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:

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}]]
2

Hi Vitaliy,

a different but similarly intriguing problem is the one of De Bruijn sequences.

There are nice Demonstrations about that: De Bruijn Graph Arcs

Combinatorica had its own function for it: DeBruijnSequence

In Mathematica you can also try:

out = FindEulerianCycle[DeBruijnGraph[3, 1], 24];
(First /@ #) & /@ out

which comes from this website.

You might like the video on this website:
https://sms.cam.ac.uk/collection/1157706

and in particular this one on how to crack a combination lock.

Cheers,

Marco

3

Thanks, Marco, indeed, the relation to De Bruijn sequences is highlighted in this paper:

Non-Uniqueness of Minimal Superpermutations, Nathaniel Johnston