A remark on 6-superpermutations of length 872

[Robin Houston]

There are actually (up to relabelling) four different known 6-superpermutations of length 872.

Because the one I found ends with 123, and there are three edges in the Hamiltonian path that also have overlap 3, we can split the superpermutation into four pieces that can be recombined in four different ways with the same overall length.

The pieces are:

• 12345612345162345126345123645132645136245136425136452136451234651234
  
• 234156234152634152364152346152341652341
  
• 341256341253641253461253416253412653412
  
• 412356412354612354162354126354123654132654312645316243516243156243165243162543162453164253146253142653142563142536142531645231465231456231452631452361452316453216453126435126431526431256432156423154623154263154236154231654231564213564215362415362145362154362153462135462134562134652134625134621536421563421653421635421634521634251634215643251643256143256413256431265432165432615342613542613452613425613426513426153246513246531246351246315246312546321546325146325416325461325463124563214563241563245163245613245631246532146532416532461532641532614532615432651436251436521435621435261435216435214635214365124361524361254361245361243561243651423561423516423514623514263514236514326541362541365241356241352641352461352416352413654213654123
  

and the other three recombinations, relabelled so they start 123456, are:

• 12345612345162345126345123645123465123415623415263415236415234615234165234125634125364125346125341625341265342165324163524613254613245613246513246153246135246315243615243165243156243152643152463512436512435612435162435126435124635214635241632541632451632415632145631245361245316245312645312465312456314256314526134526143526145326145236142536142356142365142361542361452631456231465231462531462351462315462314563215463215643215634215632416532146532164523164253164235164231564231654231645213654213652413625413624513624153621453621543621534621536421536241356214356213456213546213564213562413652143652134652136452163452164352164532165432615432651432561432516432514632514362514326541326451326415326413526413256413265431256431254631254361254316254312654321653426153426513425613425163425136425134625134265314265341235641235461235416235412635421635426135426315426351426354123654123
  
• 12345612345162345126345123645123465123415623415263415236415234615234165231465213462513642153642135642136542136452136425136245132645132465132456132451632451362541326541325641325461325416325413625143625134621534621354621345621435624135264135246135241635241365241356243156243516423516432516435216435126431526431256431265431264531264351624356124365124361524361254361245361243562145362145632145623145621346521436521463512463152463125463124563124653124635142653142651342615342613542613452614352614532614523614526314526134256143256142356142536142563142561342651432651423651426351462351463251463521465321645321654321564321546321543621543261543216534216354216345216342516342156342165324156324153624153264153246153241653214652316452316542315642315462315426315423615423165243165234125634125364125346125341625314625316425316245316254316253412653412356412354612354162354126354123654123
  
• 12345612345162345126345123645123465124365142361542631452631425631426531426351426315426135421635421365421356421354621354261534216534215634215364215346215342615432615423614523614253614235614325613425163425136425134625134265134256132456132546312546321546325146325416324516324156324165324163524163254613256413265413264513264153264135264132561435261435621435612435614236514326514362541362451362415362413562413652413625431652431654231645231642531642351643251643521643512643516243516423156432156431256431526431562431564231654321654312654316254361254362154362514365214635214653214563214536214532614532164532146523146253146235146231546231456231465213456213452613452163452136452134652143651246351246531245631245361245316245312645312465132465123415623415263415236415234615243615246315246135246153246152341652341256341253641253461253416253412653412356412354612354162354126354123654123
  

My sense is that this phenomenon means it would be rather surprising to find any n > 4 for which the minimal n-superpermutation is unique up to relabelling, but I don’t see how to definitively rule it out.

[Robin Houston]

So in other words, this Hamiltonian path has rather a special structure. It comes from a partitioning of the nodes of the graph of 6-permutations into cycles that use only the edges of weight 1 and 2.

Could we search for such a partitioning of the graph of 7-permutations?

[slepasteur]

I found this one with LKH:

12345612345162345126345123645132645136245136425136452136451234651324651342651346251346521346512341562431562413562415362415632415623415263145263154263152463512463521463524163524613526413526143562145361245361425361452361453261543621546321546231546213546215346215436125436152436154236154326153426153246153264153261453621456321456231456213456214356124356142351643251634215643215642315642135642153642156342165324165321465312465314265314625314652314653216453126453162453164253164523164532165431265431625431652431654231654321653421635421634521634251632451632541632514632516435216435126435162435164235146235142635142365143265143625143652143651243651423561432561342561324561325461325641325614352613452613542613524631526431526341523641523461523416523412563142563124563125463125643125634125364125346125341625341265341235641235461235416235412635412365413265413625413652413654213654123

It does not seems to be in the 4 you listed. Not sure if it falls in the relabelling category though because I don't really understand what relabelling means.

[Robin Houston]

Wow, that was quick! Congratulations.

Sorry, I should have been clearer. By “relabelling” I just meant applying a permutation of {1,2,3,4,5,6} to the whole thing. Since this starts with 123456, it’s in canonical form and can’t be a relabelling of anything we know about.

So I think this is a new creature hitherto unknown to humanity! Interestingly, it also splits into four pieces that represent cycles using only edges of weight 1 and 2, as follows:

• 1234561234516234512634512364513264513624513642513645213645123465132465134265134625134652134651234
  
• 234156243156241356241536241563241562341526314526315426315246351246352146352416352461352641352614356214536124536142536145236145326154362154632154623154621354621534621543612543615243615423615432615342615324615326415326145362145632145623145621345621435612435614235164325163421564321564231564213564215364215634216532416532146531246531426531462531465231465321645312645316245316425316452316453216543126543162543165243165423165432165342163542163452163425163245163254163251463251643521643512643516243516423514623514263514236514326514362514365214365124365142356143256134256132456132546132564132561435261345261354261352463152643152634152364152346152341652341
  
• 34125631425631245631254631256431256341253641253461253416253412653412
  
• 41235641235461235416235412635412365413265413625413652413654213654123
  

So it does rather look as though we might want to search for vertex cycle covers of the graph restricted to edges of weight 1 or 2.

--
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 post to this group, send email to superper...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/c8ff7e82-3df0-41ba-9da3-64b01e694936%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Simon Lepasteur]

A new one?

12345612345162345126345123645123465123415623145623154623156423156243516243561243562143562413562431562341526341523641523461523416523412563412536412534612534162534126534123564123546123541623541263542163452163425163421563421653241635241632541632451632415632416532146352146325146321546321456321465312463512463152463125463124563124653142653146253146523146532164531264531624536124536214536241536245136254136251436251346215346213546213456213465213462513642153642135642136542136452136425136245316425316452316453216543126543162543165243615423615432615342615324613524613254613245613246513264513265413265143265134265132461532641532614523614526314526134526143526413526431526435126435216435261453261543621543612543615243651243652143652413652431654231654321653421635426135426315426351423651423561425361425631425613425614325641325643125643215643251643256142351642351462351426354123654123

[Niles Johnson]

Woohoo!!  I *think* this is different from the others.  I notice it starts with 12345612345, and of the pieces that Robin made, none except for the last one have that pattern of digits number 7--11 repeating the first 5 digits in the same order.  The last piece does have that pattern, but looking at the last several digits, they don't have the same pattern as the corresponding digits in your second find (I think).

I wonder if your second find also splits in the way Robin mentioned, but I don't have any time to look right now :/

For someone who does, I think it's just a matter of Ctrl-F finding pieces like 123123, and then you split in he middle of that.

At some point, we (I) probably need Robin to explain this "weight" thing a little more.  Does something like this happen for the 5-superperms?  And why doesn't it for 4? (At least, I think it doesn't, because I thought I read that the 4-superperm was unique.)

Could a 7-superperm split along a sequence like 124123? Or 1234123?  And could an 8-superperm split along 12341234?  I think we (I) need to understand how to ask these questions in terms of the TSP to be able to understand them.

Lastly, do any of the pieces of these 6-superperms relate in an interesting way to minimal 5-superperms?  Do they even have the right length?  What if you delete all the 6s?  These are easy questions, but I just don't have time to look right now :/ Here too, I think it would be useful for someone to explain these to me in terms of the TSP :)

Great fun!

Niles

A new one?

12345612345162345126345123645123465123415623145623154623156423156243516243561243562143562413562431562341526341523641523461523416523412563412536412534612534162534126534123564123546123541623541263542163452163425163421563421653241635241632541632451632415632416532146352146325146321546321456321465312463512463152463125463124563124653142653146253146523146532164531264531624536124536214536241536245136254136251436251346215346213546213456213465213462513642153642135642136542136452136425136245316425316452316453216543126543162543165243615423615432615342615324613524613254613245613246513264513265413265143265134265132461532641532614523614526314526134526143526413526431526435126435216435261453261543621543612543615243651243652143652413652431654231654321653421635426135426315426351423651423561425361425631425613425614325641325643125643215643251643256142351642351462351426354123654123

To unsubscribe from this group and stop receiving emails from it, send an email to superpermutators+unsubscribe@googlegroups.com.
To post to this group, send email to superpermutators@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/c8ff7e82-3df0-41ba-9da3-64b01e694936%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

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 superpermutators+unsubscribe@googlegroups.com.
To post to this group, send email to superpermutators@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/CAGGS1ipAjvo0Oykm%2BwZdrQKTVNbZ%2BrpAX%2BPAw7yx1CbTEAZyYQ%40mail.gmail.com.

[Simon Lepasteur]

Yet another one:

12345612345162345126345123645123465132456132451632451362451326451324651342651346251436251463251462351426351423651423561425361425631425613425614325614235164325164352146352143652143562134562135462135642136542136452136425136421536241536214536215436215346215364213562413562143526134526135426135246135264135261435216435126435162435164235146253146523145623145263145236145231645321645312645316245316425316452314653214653124635124631524631254361245361243561243651243615243612543162543126543216543261534261532461532641532614532615432651432654132564132546132541632541362541326543125643152643156243156423154623154263154236154231654231564321563421653421635421634521634251634215632415632145632154632156431254631245631246531426531462513465213465123415623415263415236415234615234165243165241365241635241653241652341256341253641253461253416253412653412356412354612354162354126354123654123

I will make a proper merge request to the repository containing all the permutation we found but in the meantime I will continue posting new one here.

A new one?

12345612345162345126345123645123465123415623145623154623156423156243516243561243562143562413562431562341526341523641523461523416523412563412536412534612534162534126534123564123546123541623541263542163452163425163421563421653241635241632541632451632415632416532146352146325146321546321456321465312463512463152463125463124563124653142653146253146523146532164531264531624536124536214536241536245136254136251436251346215346213546213456213465213462513642153642135642136542136452136425136245316425316452316453216543126543162543165243615423615432615342615324613524613254613245613246513264513265413265143265134265132461532641532614523614526314526134526143526413526431526435126435216435261453261543621543612543615243651243652143652413652431654231654321653421635426135426315426351423651423561425361425631425613425614325641325643125643215643251643256142351642351462351426354123654123

To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/c8ff7e82-3df0-41ba-9da3-64b01e694936%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
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 post to this group, send email to superper...@googlegroups.com.

[Niles Johnson]

Cool!  I think it would be useful to put them in a format where we can see the cuts Robin does, and see whether one is a relabeling of a shuffle of another.  I don't quite know how to do that, but I guess I'll figure it out if someone else doesn't do it first.

A new one?

12345612345162345126345123645123465123415623145623154623156423156243516243561243562143562413562431562341526341523641523461523416523412563412536412534612534162534126534123564123546123541623541263542163452163425163421563421653241635241632541632451632415632416532146352146325146321546321456321465312463512463152463125463124563124653142653146253146523146532164531264531624536124536214536241536245136254136251436251346215346213546213456213465213462513642153642135642136542136452136425136245316425316452316453216543126543162543165243615423615432615342615324613524613254613245613246513264513265413265143265134265132461532641532614523614526314526134526143526413526431526435126435216435261453261543621543612543615243651243652143652413652431654231654321653421635426135426315426351423651423561425361425631425613425614325641325643125643215643251643256142351642351462351426354123654123

To unsubscribe from this group and stop receiving emails from it, send an email to superpermutators+unsubscribe@googlegroups.com.
To post to this group, send email to superpermutators@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/c8ff7e82-3df0-41ba-9da3-64b01e694936%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
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 superpermutators+unsubscribe@googlegroups.com.
To post to this group, send email to superpermutators@googlegroups.com.

[Robin Houston]

The script splitsuperperm.py is a very crude way to visualise the cycle structure of a superpermutation.

For example, if I visualise the structure of the unique minimal 4-superpermutation, like this:

bin/mkpalindromic.py 4 | bin/splitsuperperm.py 4

the output is:

1234

2341

3412

4123

...

2314

3142

1423

4231

...

3124

1243

2431

4312

...

...

2134

1342

3421

4213

...

1324

3241

2413

4132

...

3214

2143

1432

4321

Adjacent rows overlap by three characters. A row of dots denotes that the permutations either side of the dots only overlap by two symbols. And two rows of dots means they only overlap by one symbol.

Robin

A new one?

12345612345162345126345123645123465123415623145623154623156423156243516243561243562143562413562431562341526341523641523461523416523412563412536412534612534162534126534123564123546123541623541263542163452163425163421563421653241635241632541632451632415632416532146352146325146321546321456321465312463512463152463125463124563124653142653146253146523146532164531264531624536124536214536241536245136254136251436251346215346213546213456213465213462513642153642135642136542136452136425136245316425316452316453216543126543162543165243615423615432615342615324613524613254613245613246513264513265413265143265134265132461532641532614523614526314526134526143526413526431526435126435216435261453261543621543612543615243651243652143652413652431654231654321653421635426135426315426351423651423561425361425631425613425614325641325643125643215643251643256142351642351462351426354123654123

To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/c8ff7e82-3df0-41ba-9da3-64b01e694936%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
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 post to this group, send email to superper...@googlegroups.com.

[slepasteur]

Here are 7 new ones:

• 12345612435614235614325614352613452613542613524613526413526143562134562135462135642135624135621435612453612456312465312463512463152463125463124561324516324513624513264513246513245612345162345126345123645123465123415623415263415236415234615234165234125634125364215346215342615342165342156324153624153264153246153241653241563214536214532614532164532146532145632154632156432156342153642513462514365213465213645213654213652413652143651243651423651432654132564132546132541632541362541326543126453126435162431562431652431625431624531624351642351643251643521634521635421635241635214635216435126431526431256431265432165432615436215436125436152436154231654231564231546231542631452361452316452314652314562314526314256314265314263514263154236154326514362514632514623514625314625134265134256134251634251364253164253614253641253461253416253412653412356412354612354162354126354123654123
• 12345612345162435162453164253146253142653142563142536142531645231645321645312645316245136245163245613245631245632145632415632451623451263451236451234651234156231456231546231564231562431562341526341523641523461523416523412563412536412534612534162534126534123564123546123541623541263541236541326451326415326413526431526435126435216435261453261452361452631452613452163425136425134625134265134256134251634215634216534216354216345213645213465214365124361524361254361245361243561243651423561423516423514623514263514236514326514362514365214635241635246135246315246351246352146532416532461532465132465312465321465231465213456213546213564213562413562143562134526143526413256431256432154632514632541632546132546312546321543621534621536421536241536214536215432615423615426315426135426153426154321654312654316254316524316542316543215643251643256143256413265413625413652413654213654123
• 12345612345162345126345123645123465123415623415263415236415234615234165234125634125364125346125341625341265314263514263154623145623146523146253146235146231546321546312546315246315426314526314256314265312465312645316243512643521634521364521346521345621345261345216354216352416352146352164352614352641352643152643512463512436512435612435162431562431652431625431624531642531645231645321654321653421563421536421534621534261534216532415632451632541632514632516432561432564132564312564321564325163425136425134625134265132465132645132654132651432651342561342516324561324563124563214563241536241356241365241362541362451362415326415324615324165321465321645312654312653412356421356423156423516423561423564123546132546135246135426135462135461235416235412635412365421365423165423615432615436214536124536142536145236145326145362143562143652143625143621543612543615243615423651423654123
• 12345613245613425613452613456213456123451623451263451236451234651234156234152634152364152346152341652431654231564321563421653421635421634521634251632451632541632514632516435216435126435162435164235146235142635142365142356143256143526143562143561243651243615243612543612453612435614235164325163421563241563214563215463215643125643152643156243156423154623154263154236154231654321654312654316254316524136524163524165324615326415326145326154326153426153246513264513265413265143265134265132465312463512463152463125463124563124653214652314562314526314523614523164532164531264531624531642531462531426531425631425361425316452314652134652143652146352146532416523412563412536412534612534162534126534123564132564135264135624135642136542136452136425136245136254136251436251346251364215362415362145362154362153462153642135641235461325461352461354261354621354612354162354126354123654123
• 12345613245613425613452613456214356124356142356143256143526143562145362154361254361524361542361543261534261532461532641352641325641326541326451326415326145326154362153462153642135642136542136452136425136421536241356241365241362541362451362415362145632154631254631524631542631546231546321564321563421563241563214562314526314523614523164253146251346251436251463251643251634251632451632541632514623514625314265134265143265142365142635142653142563142536142531642351642315642316542316452314652134652143652146352164352163452163542163524163521465321645321654321653421653241653214652314562134561234516234512634512364512346512436512463512465312456312453612453162435162431562431652431625431624531264351264315264312564312654312645312465132465123415623415263415236415234615234165234125634125364125346125341625341265341235641235461325461352461354261354621354612354162354126354123654123
• 12345612435614235614325641325643125463125436125431624531624351624315624316524361524365124365214365241362541362451362415362413562413652431625431265432165432615432651432654132654312564321564325164325614352641352643152643512643521643526143562143561245361425361452361453264153264513264531264532164532614536214536124563142563145263145623145632145631245613246513246153246135246315246351246352146352416325416324516324156324165324163524613254613245612345162345126345123645123465123415623415263415236415234615234165234125634125364125346125341625341265341235641235461235416235412635421635426135426315426351426354123654213645213465213456213452613452163452136425134625143625146325146235146253146523146532146531246531426531462513426513425613425163425136421534621543621546321546231546213546215342615342165342156342153642135642136542316452316425316423516423156423165423615423651423654123
• 12345612345162345126345123645123465123415623415263415236415234615234165231462531426513425613425163425136425134625134265143265142365142635142653142563142536142531642531462351462315462314562314652316452316542316524361524365124365214356241356243156243516243561243562143526145321645321465324165324615324651324653124653214563241563245163245613245631245632145362415362451362453162453612453621453261452361452631452613452163452136452134652134562134526143521643521463524163524613524631524635124635214365241365243165234125634125364125346125341625341265341235642135462135426153421653421563421536421534621534261543216543215643251643256143256413265413264513264153264135264132564312654312645312643512643152643125643215463251463254163254613254631254632154362514362541362543162543612543621543261542361542631542613542163542136542135642315642351642356142356412354612354162354126354123654123