3
|
5148 Views
|
2 Replies
|
9 Total Likes
View groups...
Share

# Code & exploration of Minimal Superpermutation problem

Posted 9 years ago
 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: 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 Replies
Sort By:
Posted 9 years ago
 Hi Vitaliy,a different but similarly intriguing problem is the one of De Bruijn sequences.There are nice Demonstrations about that: De Bruijn Graph ArcsCombinatorica had its own function for it: DeBruijnSequenceIn 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/1157706and in particular this one on how to crack a combination lock.Cheers,Marco
Posted 9 years ago
 Thanks, Marco, indeed, the relation to De Bruijn sequences is highlighted in this paper:Non-Uniqueness of Minimal Superpermutations, Nathaniel Johnston