How many standard superpermutations are there length 872 for n=6?

[Mister Teacher]

In the Stand-up-Maths video and on various websites I read that Robin Houston found "A superpermutaion of length 872 for 6 characters." I have found three more.

Of course, all you have to do to get another three is switch 1 to 2, 2 to 3, 3 to 4, 4 to 1. Once you've done this the new superpermutation will not start with 123456. However somewhere in there must lie 123456, wherever was 412356 in the original. You simply slide the superpermutation around so that this is the new start. The beginning of the old superpermutation will clip on to the end, because it ends 654123. 

So here is the Houston Solution

12345612345162345126345123645132645136245136425136452136451234651234156234152634152364152346152341652341256341253641253461253416253412653412356412354612354162354126354123654132654312645316243516243156243165243162543162453164253146253142653142563142536142531645231465231456231452631452361452316453216453126435126431526431256432156423154623154263154236154231654231564213564215362415362145362154362153462135462134562134652134625134621536421563421653421635421634521634251634215643251643256143256413256431265432165432615342613542613452613425613426513426153246513246531246351246315246312546321546325146325416325461325463124563214563241563245163245613245631246532146532416532461532641532614532615432651436251436521435621435261435216435214635214365124361524361254361245361243561243651423561423516423514623514263514236514326541362541365241356241352641352461352416352413654213654123

And here is the first rotated solution:

12345612345162345126345123645123465123415623415263415236415234615234165234125634125364125346125341625341265342165324163524613254613245613246513246153246135246315243615243165243156243152643152463512436512435612435162435126435124635214635241632541632451632415632145631245361245316245312645312465312456314256314526134526143526145326145236142536142356142365142361542361452631456231465231462531462351462315462314563215463215643215634215632416532146532164523164253164235164231564231654231645213654213652413625413624513624153621453621543621534621536421536241356214356213456213546213564213562413652143652134652136452163452164352164532165432615432651432561432516432514632514362514326541326451326415326413526413256413265431256431254631254361254316254312654321653426153426513425613425163425136425134625134265314265341235641235461235416235412635421635426135426315426351426354123654123  

 

You can do this twice more to get 4 solutions.  

Pretty obvious. 

This approach also works for the n=5 strings which are two different superpermutations that have been rotated 3 times. Plus one other.    

That's not what I mean by I have found three more, I have found three others, which can be rotated in the same way to each give 4. So that's 12 plus the original 4 gives 16 solutions in total.

My question is are there any more???

  

 I have read on Greg Egans website that many others have been found not using the standard kernel. ie they do not end in 654123 or anything like that. Apparently this is how the record breaking n=7 superpermutation was found. 

I however am working within the standard kernel, I'm not interested in these freaky non standard solutions. The method I'm working with relies on them being standard. Here is one of mine:

1234561234516243516245316245136245163245162345126345123645123465123415624315624135264135246135241635241365241356241536241563214562314526314523614523164523146523145621346521346251346215346213546213456214352614352164352146352143652143562145362145632154632514632541632546132564132561432561342651324651326451326541326514326513421532461532641532614532615432615342613542613452613425613245613254631245631246531246351246315246312546321564321563421653241653214653216453216543126453126435126431526431256431265431625436124536124356124365124361524361254362154362514362541362543165243165423156423154623154263154236154231654321653421635421634521634251643251642351462351426351423651423561423516425314625314265314256314253614253164251364215364213564213654213645213642516342156324156234152634152364152346152341652341256341253641253461253416253412653412356412354612354162354126354123654123

I found this by geometrically interpreting the superpermutation and rearranging the previous solution by hand. I believe this approach could lead to a mathematical solution for all n, but it would be very useful to know how many solutions we are looking for.

[Robin Houston]

Hello Mister Teacher!

If I’ve understood you correctly, there are 42,288 superpermutations of the form you’re interested in.

You can download a compressed file containing all of them from https://github.com/superpermutators/superperm/blob/master/superpermutations/6/872-treelike.txt.gz

Cheers,

Robin

--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/d54004af-2935-4306-92a6-611ade5842d9n%40googlegroups.com.

[Mister Teacher]

WOW.

Thanks for the fast response. That is a lot of superpermutations. 

I did not think there would be so many in that form. It will be interesting to see how they all fit into my geometric interpretation. Although I think hand drawing each of them might be a little too time consuming, even during lockdown.

It seems very weird. Apart from being a huge number, 42,288 = 3x4x4x881 as a product of primes. One of the fours will be the +1/slide around I described above. I have an idea where the other 3 and 4 will come from in the geometry. But 881? What's that doing there?

[Randy Olsen]

Would interpreting the 881 as the difference or sum of two numbers suggest any meaning in your geometric interpretation?  If sum, perhaps you have an odd number of ways to implement some trick in the kernel, and an even number of ways in the extensions.  If difference, I might have a long-shot suggestion or two, but first I wanted to ask if the idea seems viable.  

Thanks, 

Randy

[nage...@gmail.com]

The string of digits after "Here is one of mine” is only 871 long, and only contains 716 permutations, so it’s not a superpermutation.

I guess something got chopped out along the way. The only single-digit addition I could find to repair it gives:

12345612345162435162453162451362451632451623451263451236451234651234156243156241352641352461352416352413652413562415362415632145623145263145236145231645231465231456213465213462513462153462135462134562143526143521643521463521436521435621453621456321546325146325416325461325641325614325613426513246513264513265413265143265134261532461532641532614532615432615342613542613452613425613245613254631245631246531246351246315246312546321564321563421653241653214653216453216543126453126435126431526431256431265431625436124536124356124365124361524361254362154362514362541362543165243165423156423154623154263154236154231654321653421635421634521634251643251642351462351426351423651423561423516425314625314265314256314253614253164251364215364213564213654213645213642516342156324156234152634152364152346152341652341256341253641253461253416253412653412356412354612354162354126354123654123

(this involved inserting a 6 after the 324th digit of the original).

As you  note, there is a 4-element symmetry group, generated by the cycle (1234), that preserves the standard kernel (i.e. the first 3-cycle of the standard n=6 superpermutation). This can be extended to 8 elements by the action of reversing the order of the digits in the superpermutation and then applying the permutation [321456] to all the digits, which maps the reversed 654123, i.e. 321456, back to 123456.

The repaired version of the superpermutation you give can be obtained from the one you call “the Houston Solution” by one of those 8 elements (specifically, using [412356] and rotating the new occurrence of 123456 to the start, followed by the reversal/renumbering operation ).

Are you able to give a formal description of the second 4-element group of transformations, that you say is able to produce 16 distinct superpermutations?  Clearly one element of it is equivalent to the reversal/renumbering operation I’ve described.

BTW, I wouldn’t expect to be able to account for the entire factorisation of the total of 42,288 in terms of these kinds of transformations that preserve the standard kernel and act without fixed points (at least, the 8-element group I’ve mentioned has no fixed points, so it partitions the 42,288 superpermutations into 5286 equal-sized orbits). At a finer level of detail, there’s a vast menagerie of different structures among the 42,288 — for example, if you draw them as 2-cycle graphs, there are hundreds of different isomorphism classes of graphs. So there will be other, more restricted transformations acting on various subsets of the total, and generally speaking they won’t even have equal-sized orbits.  So the factor of 881 is most likely to consist of hundreds of different terms, each one the size of an orbit for some more restricted group of transformations.

[Randy Olsen]

I've checked all 42,288 of the length 872 n=6 superpermutations in this "treelike" solution set from Robin Houston against all 96 length 873 "standard" superpermutations in Nathaniel Johnston's original (before discovery of length 872 solutions) file (at http://www.njohnston.ca/superperm6.txt) to evaluate the spans where a "standard" superpermutation can match any of these length 872 superpermutations.

The maximum span of alignment anywhere is 145.  That is, they can match exactly for just at or under 1/6 of the way.  So, they can bag about 120 of the 720 permutations in the exact same way and a length 872 superpermutation must find its advantage over the "standard" superpermutation in bagging the remaining 5/6 of the permutations.  

In the over four million pairings, this result is far from unique, though.

From spot checking, it appears each "standard" superpermutation tends to find 526 partners from the "treelike" solution set with which to achieve alignment of length 145.

Plenty of cases of alignment 144 also exist.

For a given pair of "standard" superpermutation and length 872 superpermutation from the "treelike" set, such spans of alignment like 145 or 144 can only be achieved once. That is, a superpermutation pair can and frequently does match for the first 145 or 144 digits, and then they go separate ways, but they do not resume such matching for the last 1/6 of the way, for example.

After a matching span of 145 or 144 digits, the longest you can find the same pair to resume matching exactly is a span of 35 or 36 digits, respectively.

I just wrote a little bit of C++ code to find these alignment results, and I was pleased the computational time for comparing 4,059,648 pairs of n = 6 superpermutations was not more than a few minutes.

If we consider the 1st, 2nd, 3rd, and 4th longest stretches of exact matching for a given pairing, the following cases, each of which has just a handful (eight or so) total instances in the over four million pairings, might be argued as "most aligned":

145-35-8-3,

144-36-8-4,

145-28-12-7

For each of these cases, I'm sharing below one of the explicit pairings, and I have adjusted white space to highlight where they match and where they don't.  In particular, I have indented the matching stretches.

Please consider this first case:

1234561234516234512634512364512346512341562341526341523641523461523416523412563412536412534612534162534126534123564123546123541623541263541236541

23146523146253146235146231546231456231426531426351426

31542631

452631425631423651423615423614523614253614235614231654231645231642531642351642315642312456312453612453162453126453124653124356124351624351264351246351243651243156243152643152463152436152431652431256431254631254361254316254312654312134562134526134521634521364521346521342561342516342513642513462513426513421563421536421534621534261534216534213564213546213542613542163542136542132456132451632451362451326451324651324156324153624153264153246153241653

24135624135264135246135241635241365

24132564132546132541632541362541326541321456321453621453261453216453214653214356214352614352164352146352143652143256143251643251463251436251432651432156432154632154362154326154321654321

1234561234516234512634512364512346512341562341526341523641523461523416523412563412536412534612534162534126534123564123546123541623541263541236541

32654312564321564325164325614325641325643125463215462

31542631

542361542316542315642315462135462153462154362154632514623514263514236514235614235164235146253142653142563142536142531642531462513462514362514632541632546132546312456321456231456213456214356214536241536245136245316245361245362145632415632451632456132456312465321465231465213465214365214635214653241653246153246513246531246351243651243561243516243512643512463152436152431652431562431526431524631254361254316254312654321654326154326514326541362541365

24135624135264135246135241635241365

4213645216342516342156342165342163542163452164352164532614523614526314526134256134265134261534261354261345261435261453264153264513264531264532164523164521364251364215364213564213654123

The top part is a length 873 superpermutation (for n=6) from Nathaniel Johnston's original file of 96 such superpermutations, and the bottom part is a length 872 superpermutation from Robin Houston's "treelike" solution set of 42,288 such superpermutations.

I've indented lines where this pair of superpermutations matches exactly for spans exceeding the length of an individual permutation.

This pair starts off identical for a span of 145, then later matches exactly again for a span of 8, and then sometime later aligns for a span of 35.

Second case:

123456123451623451263451236451234651234156234152634152364152346152341652341256341253641253461253416253412653412356412354612354162354126354123654

1231456231452631452361452316452314652314256314253614253164253146253142653142356142351642351462351426351423651

42315642

315462315426315423615423165423124563124536124531624531264531246531243561243516243512643512463512436512431562431526431524631524361524316524312564312546312543612543162543126543121345621345261345216345213645213465213425613425163425136425134625134265134215634215364215346215342615342165342135642135462135426135421635421365421324561324516324513624513264513246513241563241536241532641532461532416532413562413526413524613524163524136524132564132546132541632541362541326541321456321453621453261453216453214653214356214352614352164352146352143652143

256143251643251463251436251432651432

156432154632154362154326154321654321

123456123451623451263451236451234651234156234152634152364152346152341652341256341253641253461253416253412653412356412354612354162354126354123654

2136524136254136245136241536241356214356213456213546215346215436215463215462315462135642153642156342156432156

42315642

135624136521436521346521364521365423165423615426315426135246132546132456132465132461532461352641325641326541326451326415326413526143526134526135426153426154326154236514235614253614523614532614536214536124536142563145263145623145632145631246531426531462531465231465321645312645316245316425316452316453216543216534216532416352146352164352163452163542163524163254163245163241563241653214653124635124365124356124351624351264351246315243615243165243156243152643152463125436125431625431265431256431254631245631425613425163425136425134625134265134

256143251643251463251436251432651432

56142351642351462351426351423654123

Again, the top part is a length 873 superpermutation (for n=6) from Nathaniel Johnston's original file of 96 such superpermutations, and the bottom part is a length 872 superpermutation from Robin Houston's "treelike" solution set of 42,288 such superpermutations.

Again, I've indented lines where this pair of superpermutations matches exactly for spans exceeding the length of an individual permutation.

This pair starts off identical for a span of 144, then later matches exactly again for a span of 8, and then sometime later aligns for a span of 36.

Similarly, the third case:

1234561234516234512634512364512346512341562341526341523641523461523416523412563412536412534612534162534126534123564123546123541623541263541236541

23145623145263145236145231645231465231425631425

3614253164253146253142653142

35614235164235146235142635142365142315642315462315426315423615423165423124563124536124531624531264531246531243561243516243512643512463512436512431562431526431524631524361524316524312564312546312543612543162543126543121346521346251346215346213546213

4562134

265134261534261354261345261342561342165342163542163452163425163421563421365421364521364251364215364213564213245613245163245136245132645132465132415632415362415326415324615324165324135624135264135246135

241635241365

24132564132546132541632541362541326541321456321453621453261453216453214653214356214352614352164352146352143652143256143251643251463251436251432651432156432154632154362154326154321654321

1234561234516234512634512364512346512341562341526341523641523461523416523412563412536412534612534162534126534123564123546123541623541263541236541

32654312654321654326153426153246153264153261452

3614253164253146253142653142

56314253614235614236514236154231654231564231546231542631542361452631452613452614352614532615432651432654136254316254361245316245312645312465312456312453612435612436512436152431652431562431526431524631524361254362153462153642153624153621456321456231

4562134

562143562145362154362514362541365241356241352641352461352416325461325463125463215463251463521465321465231465213465214365214635124635142635146235146325416324513624513264513246513245613245163241563241653

241635241365

4213564213546213542613542163452164351264351624351642351643256143256413256431256432156432516435216453216452316452136452163425136425134625134265134256134251634215634216534216354213654123

This pair starts off identical for a span of 145, then later matches exactly again for a span of 28, then later again aligns for a span of 7, and then sometime later aligns for a span of 12.