A “tight” superpermutation on 5 symbols

[Robin Houston]

Greg Egan has found a “tight” superpermutation on 5 symbols. In other words, it uses only edges of weight 1 and 2 in the graph; or to put it another way no two consecutive symbols are ever wasted in the sense of not producing a new permutation.

It has length 154, which is one longer than the eight minimal superpermutations on 5 symbols:

1234512341523412534215342513425314235142315423145213452143521453241532451324531243512431524312543215432514325413524135421354123541325431245321452314253412

I’ve added it to the git repository in the file superpermutations/5/154-tight-egan.txt

It’s interesting – as Greg says on Twitter – that it’s one symbol longer than the minimum length known in general, which is also true for 6 symbols: see the tight superpermutations here. (It’s also possibly interesting that in all these examples the edge from the end back to the beginning has weight 3.)

I’ve invited Greg to join this group if he likes.

Cheers,

Robin

[Greg Egan]

I found a total of 39 tight superpermutations on 5 symbols, which is an exhaustive list of those meeting the following conditions:

• Only edges of weights 1 and 2

• No consecutive edges of weight 2

• The initial 10 edge weights are 1 1 1 1 2 1 1 1 1 2

• The total length of the string is 154

All 39 of these end at 53412.

1234512341523412534215342513425314235142315423145213452143521453241532451324531243512431524312543215432514325413524135421354123541325431245321452314253412

1234512341523412534215342513425314235142315423145213452143524135421354123541325431254321543251432541352431524351243521453241532451324531245321452314253412

1234512341523412534215342513425314523145321453124351243152431254321543251432541324513241532413521435213452135423154235142354123542135241325431245314253412

1234512341523412534215342513425314523145321435213452135423154235142354123542135241325413245132415324135214325143215432145312435124315243125431245314253412

1234512341523412534215342513245312453214523145213452143524135243154235142354123542135423154321543125431524351243521453241532451325413251432513425314253412

1234512341523412534215324135241325413245132415321452314521345214351243152431254312453124351423541235421354231542351432514352145321543215342513425314253412

1234512341523412531425312453125431524315423154321534215324153214523145213452143512435142351432513425132451325413524135421354123541325143521453215431253412

1234512341523412531425312453125432154325143254132451324153241352431524351243521453214523145213425134215342135423154235142354123542134521435241325431253412

1234512341523412531425312453214523145213425134215342135423154235142354123542134521435241352431524351243521453241532451324531254321543251432541325431253412

1234512341523412531425312453214523145213425134215342135412354132541352413542134521435124351423514325143521453241532451324531254315243154231543215431253412

1234512341523412531425134251432514235142531245321452314521345214352413542153421543215423154213541235413254135243152435124352145324153245132453125431253412

1234512341523412531423514231542314523142531245321453241532451324531254321543251432541352431524351243521435241354213452134251342153421354123541325431253412

1234512341523412531423514231542314523142531245321435241354213452134251342153421354123541325413524315243512435214325143215432145324153245132453125431253412

1234512341523412531423514231542314521345214352413542135412354132514325134251324513254135243152435124352145321543215342153241532145231425312453125431253412

1234512341523145231542315243152341253142531245321453241532451324531254321543251435214351243514235143254135241354213452134251342153421354123541325431253412

1234512341523145231542315243125431245321435214325142351425314251342153421354123541325413524135421345213425143215432145324153245132453124351243152341253412

1234512341523145231542351423541235421352413521435213452135423152431254312453124351243152341253421532415321453215432153425132451325413251432513425314253412

1234512341523145231542351423541235421352413521435213452135423152431254321543251432541325431245321453241532451324531243512431523412534215342513425314253412

1234512341523145231542351423541235421352413254132451324153241352143251432154321453214352134521354231524312543124531243512431523412534215342513425314253412

1234512341523145231542351423541235421345213425134215342135423152435124352143524135243152341253142531245321453241532451324531254321543251432541325431253412

1234512341523145231542351423541235421345213425134215342135423152435124352143251432154321453214352413254132451324153241352431523412531425312453125431253412

1234512341523145231542351423541235421345213425132451325413251432513421532415321453215432153421354231524351243521435241352431523412531425312453125431253412

1234512341523145231542351425314251342514325142354123542135241325413245132415321453215432153421532413521435213452135423152431254312453124351243152341253412

1234512341523145231542351432514352143512435142354123542134521342513421532413524132541324513241532145321543215342135423152431523412531425312453125431253412

1234512341523145213452143521453214523154235142354123542135423152431254321543251432541324513241532413524132543124531243512431523412534215342513425314253412

1234512341523145213452143521453215432153421532413524132541324513241532145231542351425314251342514325142354123542135423152431254312453124351243152341253412

1234512341523145213452143512435142351432513425132451325413524135421354123541325143521453215432153421532415321452315423152431523412531425312453125431253412

1234512341523145213452143512435142351432541352413542135412354132543125432154325143521453241532451324531245321452315423152431523412534215342513425314253412

1234512341523145321453124531425314523154235142354123542134521342513421534213542315243512435214352413254312543215432514325413245132415324135243152341253412

1234512341523145321453124531425314523154235143254132451324153241352413254312543215432514352143512435142354123542134521342513421534213542315243152341253412

1234512341524315241352415324513245312453214523145213452143512435142354123542135423154235143254132543125432154325143521453241523412534215342513425314253412

1234512341524315241352415321452314521345214351243514235412354213542315423514325134251324513254132514352145321543215342153241523412531425312453125431253412

1234512341524315241354213452134251342153421354123541325431254321543251435214351243514231542314523142531423514325413524153245132453124532145324152341253412

1234512341524315241354215342154321542315421354123541325143521453214523145213452143512435142351432513425132451325413524153241523412531425312453125431253412

1234512341524315423154321543125431524135421354123541325413524153245132453124532145231452134521435124351423514325143521453241523412534215342513425314253412

1234512341524315423145231425314235143251435214351243514231543215431254315241354213452134251342153421354123541325413524153245132453124532145324152341253412

1234512341524312543124531243512431524135421354123541325143251342513245132541352415321452314253142351423154231452134521435214532154321534215324152341253412

1234512341524312543124531243512431524135421534215432154231452134521435214532145231425314235142315421354123541325143251342513245132541352415324152341253412

1234512341524312543124531425314523145321435214325134215342135423154235142354123542134521342513245132541325143215432145312435124315241352415324152341253412

[Robin Houston]

Amazing! Thanks. I’ve updated the file.

--
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/c6b04c14-ed18-4306-b68f-a44214ca4d7d%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Roland Bolz]

Dear Greg,

any straightforward explanation why there's 39? I'm working on ideas for classifying superpermutations, and on different types on equivalence between them. 39 might be 3 x 13? I'd be curious to hear your ideas on this.

Warmly, R