[r-t] Superpermutations

[Philip Earis]

Things have been rather quiet on here recently, so I'd like to rouse
everyone from their slumbers.

Inspired by a recent mention on the Boston change ringers mailing list,
I've become aware of superpermutations.

As the wikipedia page (https://en.wikipedia.org/wiki/Superpermutation)
explains, a superpermutation on n symbols is a string that contains each
permutation of n symbols as a substring.

To think about it in more of a change ringing way, it's the shortest
possible way of having all n! permutations without having to do this in n!
discrete rows.

There seems to have been lots of recent activity in the field of
superpermutations, both from a combinatorial mathematics perspective and
also at applying this to bell ringing.

See for example these three links:
http://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html#NEWS2
https://arxiv.org/abs/1408.5108
https://www.youtube.com/watch?v=_tpNuulTeSQ

In the youtube video and comments beneath this, there is various
discussion about applying superpermutations to change ringing. A chap
called Kurt Ludwick
points out:

===
If we stick to standard change ringing rules, superpermutations can be
embedded in change ringing patterns for 3 or 4 bells.

On 3 bells: the optimal (length 9) superpermutation 312313213  is embedded
in the following method (starting after the leading 1 2):
123 / 123 / 132 / 132

On 4 bells: the optimal (length 33) superpermutation cannot be rung, since
it contains a "121"-type subsequence halfway through. However, the
following method contains a superpermutation of length 34 (also starting
after the leading 1 2):
1234 / 1234  /1324 / 3124 / 3214 / 2314 / 2134 / 2143 / 2413

This is the minimal change-ringable (?) superpermutation on 4 bells.

For more than 4 bells: superpermutation change ringing methods are
possible if we relax the definition of "superpermutation" to allow for
some repeated permutations (i.e., each occurs at least once, rather than
exactly once). The shortest such superpermutation I've found for 5 bells
has length 160, embedded within a method of 33 changes. I suspect this may
be minimal for 5 bells, but can't say for sure
===

Perhaps more excitingly, on 27 February this year Robin Houston and Greg
Egan found a superpermutation for n=7 of length 5906, breaking the
previous record. This built on their finding a superpermutation of length
872 for n=6. The n=7 superpermutation is copied below.  You can listen to
this being performed (on a piano) at
https://www.youtube.com/watch?v=n4WpyNMfQ2Q.

Lots of avenues to explore here. Can anyone arrange "superpermutation
blocks" for 5 or 6 bells, both with and without jump changes?




12345671234561723456127345612374561327456137245613742561374526137456213745612347561324756134275613472561347526134756213475612345761234516723451627345162374516234751623457162345176234512673451263745126347512634571263451726345127634512367451236475123645712364517236451273645123764512346751234657123465172346512734651243765124367512436571243651724365127436512473651246375124635712463517246351274635124763512467351426735146273514672351467325146735216473521674352167345216374521634752163457216345271634521764352176453271645327614532764153276451326745132647513264571326451732645137264531726453712645372164537261453726415372645132764531276453217645231764521376452173654217365241736521473652174365217346521736452176345216735421637542163574216354721635427163542176354216735241637524163572416352741635247163524176352416735214673512465371246531724653127465312476531246753142675314627531467253146752316475321647531264753162475316427531647253164752316745321674531267453162745316724531674253167452316754231675243
 1675234167523146753214675312465731246513724651327465132476513246715324671352467132546712354671253467125436715243671542367154326751432675413267543126754321675432617453621745361274536172453617425361745236174532617435261743256174326517423651742635174265317426513742651734261573426175342167534217653421756342175364217534621753426173542617345261734256173426517432615743621574361257431625743126574132657412365741263574126537412657341265743125674132567412356741253674125637412567341256743125764132576143257613425761324576132547613257461325764123576412537614253761245376125437615243761542376154327615437261543762154376125347612537461253764125736412576341257643125746312574361527436157243615742361574326175436217543612754361725436175243617542361754326715436271543672154367125463712546731254763125473615247361542736154723615473261457362145763214756321476532147635214763251476321547632145762314576213457621435762145376214573612457361425736145273614572361457326147536214753612475361427536147253614752361475326
 1473526147325614732651472365147263514726531472651347265143726514732615473621547361254731625473126547132654712365471263547126534712654371625347162537416253714625371642537162453716254371652437165423716543271654372165437126547312564713256471235647125364712563471256437215643725164327561432756413275643127564321756432715643275164325716342517634251673425163742516347251634275163425716324517632451673245163724516327451632475163245716325471632574163257146327514632715463271456327146532714635271463257164352716435721643571264351726435127643512674351264735126437512643571624351762435167243516274351624735162437516243571642351764235167423516472351642735164237514623751426375142367514237651427365142763514276531427651342765143276514237561423576142356714325671435267143562714356721435671243561724356127435612473561243756124357612435671423561742356147235614273561423751642357164325176432516743251647325164372561437256413725643172564371256473125467132456713246571324675132461573246175324617352461732541672354176
 2354716235476123547621354762315467231546273154623715462317564231576421356742135647213564271356421735624137562413576241356724135627413562471356241735621473562174356217345621735462173564213756421357642153746215374261537421653742156374215367421537642157364215763421576432157642315674231564723156427315642371564231756243157624315672431562743156247315624371562431756234157623415672341562734156237415623471562341756231475623174562317546321745632174653217463521746325174632157463217546312754631725463175246315724631527463152476315246731524637152463175426315742631547263154276315426731542637154263175462315746235174623571462357416235746123574621357462315476235147623541726354172365417235641723546172354167253417625314762531746253176425317624531762543176524317654231765432176543127654317265431762534172653417256341725364172534617253416725431672541367251436725134672153476215347261534721653472156347215364721534672135467213456721346572136457213654721365742136572413657214365721346752136475213674521367542136
 7524136752143765214375621437526143752164375214637251463721546372145637214653721463572146375214367521346725136472513674251367245136725416372541673254176325417362514736251743625173462571364257136245713625471362574136257143625713462751364275136247513627451362754163275416237541263754123675412376541327654137265413762514376251347625137462513764251376245137625413765241376542137654123756412375461327546137254613752461375426137546213754612375416273541267354127635412736541273564127354612735416275341267534127653412756341275364127534612753416275431627541362751436275134627153426713542671345267134256713426571432657142365714263571426537142657314265713426751342671534276153427165342715634271536427153462713546271345627134652713645271365427136524713652741365271436527134625731462573416257346125734621573462517364251736245173625417326541732564173254617324561732465173246153724615327461532476153241675324165732146573216457312645731624573164257316452731654273165247316527431652734165273146527316457231654723165
 74231657243165723416572314657231645732165473216574321657342165732416537241653274165324716532417653241567321456731245637124563172456312745631247563124576312456731425637142563174256314725631427563142576314256731452637145236714532671453627145367214536712453671425367145237614523716452371465237416523746152347651234765213476523147652341765234716523476152346715234617523461572346152734615237465123746521374652317465237145623714526317452631475263145726314527631452673145627314567231456732154673215647321567432156734215673241563724156327415632471563241756324157632415367241536274153624715362417536241573624153762415326741532647153264175326415732641523764152367415236471523641752364157236415273641526374152634715263417526341572634152763415267341526437152643175264315726431527643152674315264731526413752641357261435726134572613547261357426135724613572641352761435276134527613542761352476135274613527641352674135264713526417352641