Message Boards Message Boards

Code & exploration of Minimal Superpermutation problem

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.

enter image description here

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:

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}]]
POSTED BY: Vitaliy Kaurov
2 Replies

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

POSTED BY: Marco Thiel

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

Non-Uniqueness of Minimal Superpermutations, Nathaniel Johnston

POSTED BY: Vitaliy Kaurov
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract