# [r-t] Superpermutations

Glenn Taylor gaataylor at blueyonder.co.uk
Wed May 22 12:08:13 BST 2019

```Thanks, Philip.

This is not a topic that I am familiar with, but it reaches towards the answer to a question that came to my mind quite some time ago: what is the shortest string of digits that needs to be entered into a 4-digit burglar alarm to test all the possibilities without trying them all in turn.

Unfortunately n>5  (q.v. Wikipedia article)...

Cheers,

Glenn

-----Original Message-----
From: ringing-theory [mailto:ringing-theory-bounces at bellringers.org] On Behalf Of Philip Earis
Sent: 22 May 2019 09:56
To: ringing-theory at bellringers.org
Subject: [r-t] Superpermutations

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.

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

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
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

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

_______________________________________________
ringing-theory mailing list
ringing-theory at bellringers.org
https://bellringers.org/listinfo/ringing-theory

```