to Superpermutators

Someone has posted a new record-breaking superpermutation for n=7 in the comments to Matt Parker’s YouTube video. I’ve invited him to share more details here.

It has length 5907, and the tree-like structure that we expected. I attach a diagram of its 2-cycle graph.

to Superpermutators

I’ve just noticed the triangle in this graph. So it isn’t precisely what we expected at all!

to Superpermutators

I have some questions to help me understand the graph. If it's something I can read up on, just let me know what to search for. :)

What does the notation on a node mean? (eg. 3/168524)

to Justin Hoffman, Superpermutators

to Justin Hoffman, Superpermutators

to Superpermutators

This does help support the theory that the length is n! + (n-1)! + (n-2)! + (n-3)! + n - 4, for all n >= 3

to Superpermutators

We need to understand how the triangle is traversed. This opens up new possibilities that we haven’t considered – or I haven’t, anyway.

It may be significant that there is a single 1-cycle, [1456732], that is common to all three 2-cycles in the triangle [1/245673], [6/145732], [3/145672].

Here is the order in which the superpermutation traverses of all three of these 2-cycles. There are three columns, corresponding to the three 2-cycles. The annotation +++ indicates that a new 1-cycle is starting in that column. The shared 1-cycle is shown in all three columns.

I think this is a type of structure that we haven’t considered at all so far.

Best wishes,

Robin

to Superpermutators

Okay, sorry… on reflection, this is a total red herring.

This structure is not essentially different from the ones we’ve been considering, and the exact cover algorithm we used to enumerate superpermutations for n=6 will find structures such as this.

(Possibly it IS interesting that the entire structure is anchored to a single node of the principal 4-cycle?)

So I guess the real question is – how was this found? I hope the man who found it will swing by and explain!

Robin

to Superpermutators

Congratulations to Charlie Vane!  I hope he’ll describe how he found this.

And thanks to Robin for explicating the structure!

In case anyone finds it helpful, I’ve placed a version of this superpermutation (with the digits numbered 1-7) here:

to Superpermutators

Hi,

I should explain: after I saw the numberphile video on superpermutations a year ago, I saw it as solvable and got to work on it - please bear in mind that I'm an algorithm specialist more than a mathematician per say, so here's what I noticed - I'll start with #6:

In short, to construct a superpermutation you need a 'kernel' and a set of 'extensions'

1. the kernel is an initial path you start with.

as a working example, let's say that for #6 you start with the kernel as:

012345012340512340152340125340123540123045123041523041253041235041230541230145230142530142350142305142301542301245301243501243051243015243012543012

which has a length of 147, and it looks like this:

starting from the very top-left corner in the image above

- thin red lines represent 1-edges (corresponding to stuff like 012345 ⇒ 123450 // abcdef ⇒ bcdefa)

- blue lines represent 2-edges (corresponding to stuff like 012345 ⇒ 234510 // abcdef => cdefba)

- green lines represent 3-edges (corresponding to stuff like 012345 ⇒ 345210 // abcdef => defcba)

2. 'extensions' are, well, extensions to a kernel: you replace a 1-edge going from node A to B with a whole path that starts with a non 1-edge from A, connects to (only) previously unconnected nodes, and then connects back to B through another non 1-edge, like this:

the above corresponds to the best kind of extension, as ratio between newly added path length (5*[2] + 5*4*[1] - [1] = 29) to newly connected nodes (24) = 1.208...

(the added path length per extension is 29 because we also remove a 1-edge from the initial connected graph)

and keeping on extending:

and so on, until after 25 extensions we have all the nodes connected, with a total length of 147 (kernel) + 25 * 29 (extensions) = 872:

now, i think it's easy to explain both that the chosen extension is minimal, and that the chosen kernel is also minimal, along with these 2 other kernels:

which is of length 292, and with 20 extensions added comes also at a total length 292 + 20*29 = 872

(don't mind the odd green edge going back to the start - I use a path that closes in on itself, for easier coding)

and:

of length 437, which with 15 extensions also gives a total length of 437+15*29 = 872

my backtracker found a total of 42288 such solutions for the first kernel, 772 more for the second, and 16 more for the third.

the same things can be said of #7:

a kernel of size 249:

minimal extension with size 6*[2] + 6*5*[1] - [1] = 41:

keeping in mind that the above kernel connects 7*6*5 = 210 nodes and each new extension adds 7*5 = 35 nodes, to fully connect the 5040 nodes of #7 we need (5040 - 210) / 35 = 138 extensions. A fully connected superpermutation for #7 would thus have a length of 249 (kernel) + 138 *41 (extensions) = 5907 symbols

one such example solution for #7 among 20 I've found:

012345601234506123450162345012634501236450123465013245601324506132450163245013624501326450132465013426510342651304265134026513420653140265314062531406523140653214065312406531420653412065431206541320654123065412036541206354120653421065432106542310654213065421036542106354210653420165432016542301654203165402316504231650243165023416052341065234105623410526341052364105234610523416025341062534102653410256341025364102534610253416023541062354102635410236541023564102354610235416023451062345102634510236451023465102345610234516032451063245103624510326451032465103245610324516034251604325160423516042531604523160453216045312604531620453160245316042513604251630425160345216035421605342160543216054231605421360542163054216035241603521460352164035216043521603451260354126053412605431260541326054123605412630541260351426305142635014263510426351402635142063514260351246035126403512604351260345162034561203546210354620135462031546203514623054162305461230546213054623105462301546230514623501462351046235140623514602351462035416203546120356412053641205634210564321056423105642130564210356421053642105634201564320156423015642031564201356420153642015634205164320516423051642035164205316402513640251634025164302516403256143025614320561432506143256014325610432561403256410325461032541603254106325410362541032654103256401325460132540613254016325401362540132654013256403125604312560341256031425603124560312546031256403215604321560342156032415603214560321546032156403251640235164025316405231640532164053126405316240536124503612540361250436125034612503641250361425306142536014253610425361402536142053614250361245306124536012453610245361204536124053621450362154036215043621503462150364215036241503621453062145360214536201453621045362140536241053264105324610532416053241065324105632410536240153264015324601532406153240165324015632401536240513264051324605132406513240561324051632405136240531642051364205163420561342506134256013425610342561304256134025613420563140256314052631405623140563214056312405631420563412056431205641320564123056412035614230561423506142356014235610423561402356142035612403562140356241035624013562403156240351624035612043562104356201435620413560241365024136052413602541360245136024153602413560421350642135046213504261350421635042136504213560412350641235046123504162350412635041236504123560413250641325046132504163250413625041326504132560413526014352601345260135426015342601543260154236015426301542603152460315264031526043152603415260314526031542601352460135264013526041356204315620435162043561203456210345620134562031456203415620345160234156023145602315460231564023156042315602431560234165023146502316450231654032165043216503421650324165032146503216450321654031265043126503412650314265031246503126450312654031625043162503416250314625031642501364250163425016432501642350164253016452301645320164530216453012645301624530164250316245031625403165240361524036512403652140365241036524013652403165420136542016354201653420615432061542306154203615420631540261354021635402136540213564021354602135406213540261534021653402156340215364021534602153406215340261543021654302156430215463025146320541632054613205463120546321054632015463205146325014632510463251406325146032514630254163024516302415630241653024163502416305241630254613024561302465130246153024613502461305264130256413026541302645130264153062413506241305624130652413062541306245130624153064215304621530426153042165304215630421536042153064125304612530416253041265304125630412536041253064152304615230416523041562304152630415236041523064153204615320416532041563204153620415326041532064153026413502641305261430521643052146305214360521430652143056214305261340521634052136405213460521340652134056213405261304521630452136045213064521304652130456213045261305426103524610352641035261403526104352610345261035426105342610543261054236105426310542613052461302546310245631042563104526310456231045632104563120456310246531042653104625310465231046532104653120465310246351024365102435610243516024351062435102643510246315042631504623150463215046312504631520463512046352104635201463520416352046135204631502463105243610524316052431065243105624310526431052463102543610254316025431062543102654310256431025463012456301425630145263014562301456320145630214563012465301426530146253014652301465320146530214653012463501243650142365104236514023651420365142306514236051423650143265104326514032651430265143206514326051432650143625104362514036251430625143602514362054136205431620543612054362105436201543620514362501436520413652043165204361520436512043652104365201436502143560214350621435026143502164350214635021436501243560124350612435016243501264350124630512436051243065124305612430516243051264305124630152436015243061524301652430156243015264301524630125436012543061254301625430126543012564301254630215436021543062154302615403261504326150342615032461503264150326145302614532061453260145326104532614053261450326154023615042361502436150234615023641502361452036415203645120634521063452016345206134520631450263145062314506321450631245063142506314520634150263415062341506324150634215063412506341520634512064352106435201643520614352064135206431502643150624315064231506432150643125064315206435120645310264531062453106425130642510364251063425106432510642351064253106452310645321064531206451320465132045613204516320451362045132604513206451230465123045612304516230451263045123604512306451203645210364520136452031645203614523061452360145236104523614052361450236154026315406231540632154063125406315240635124063521406352410635240163524061352406315420613542061534206513426051342650134625103462513046251340625134602513462053146025314605231460532146053124605314260531462053416205346120534621053462015346205134625013465203146520341652034615203465120346521034652013465021345602134506213450261345021634502136450213465012340561234051623405126340512364051234605123406512340156234015263401523640152346015234061523401652340125634012536401253460125340612534016253401265340123564012354601235406123540162354012635401236540123

looking like:

makes any sense so far ?

Bogdan Coanda

unread,

to Superpermutators, bogdan...@gmail.com

to Superpermutators

Hi Bogdan

Thanks for the explanation, and congratulations on the results!

I’m curious to know how long your algorithm had to run to find the 20 solutions you mentioned for n=7.  Are we talking hours, days, weeks, or months?

Best wishes

Greg

to Superpermutators

It looks as if each of Bogdan’s individual extensions is what we have been calling a 2-cycle, so his approach is essentially a matter of choosing a set of 2-cycles that covers all the remaining permutations, which is isomorphic to what Robin Houston has been doing with exact covers.  (I’ve been conducting slightly less general searches by looking for induced trees in the 2-cycle graph, which could not have found the n=7 example that was posted on the YouTube comments, because it is not strictly a tree.)

So we all seem to have converged on similar approaches!  And I’m still optimistic that there will turn out to be a family of directly constructible induced trees for arbitrary n.

to Superpermutators

I believe this is also the same approach I used as well.  I didn't really name things, but I have an initial start, the kernel here, and attempt to add 25 more sets, extensions here, recursively. That is, it's perfectly fine and necessary, to, to use this terminology, add an extension within another extension. Unlike the other result for 7, I think 6 will always form a tree, or container structure.  That is, imagine the structure as a series of containers. The interior of each container is a 1 cycle, and the wall between two containers is a 2 cycle (shared) or 3 cycle, (not shared).  For n=6, you start with 4 containers. In those containers you place other containers (the extensions here). How you nest these additional containers determines the final sequence.

to Superpermutators

So we're all agreed on the general construction, and the remaining issues are:

(A) If this must be done by a brute force search, what is the most efficient way to do that? That's why I’m curious to know how long it took for Bogdan to find these n=7 results. Is it just that he’s been running a search much longer than anyone else, or is he doing something vastly more efficient than any of us have been doing?

(B) Is there a construction that directly generates a single example for each n, analogous to what I did with the Williams construction?

to Superpermutators

The key for me to finding solutions for #7 were 'tuples': sets of 5 extensions done at the same time, allowing me a backtracker of 

24+18 = 42 levels (24 tuples + 18 individual extensions)

instead of 

138 levels (individual extensions needed)

- found the #7 solutions in hours, on my iPad, python code

But I need to do some in-depth explaining:

From all the solutions found for #6, a few stood out as 4-way symmetric like the following example:

notice that the only difference between the above four is a single extension from the initial kernel.

So, considering the initial kernel for the above, I've highlighted the start nodes for the top 2 extensions, and the end nodes for the bottom bottom two extensions:

012345012340512340152340125340123540123045123041523041253041235041230541230145230142530142350142305142301542301245301243501243051243015243012543012

And now, having these four points set, we 'walk' them together, in sync, but walking the two end-points in reverse to the two start-points

'Walking' a 2-link (L2) means transforming the above set as:

123450 ⇒ 345021 // (walking forward)

to Superpermutators

Ok, I wanted to add a list of the various optimisations I had to do for the backtracker to be fast enough, but I remembered along the way the following argument for the lower bound I propose:

to Superpermutators

Hi Bogdan

Thanks for the detailed explanation.  That’s ingenious!

I want to try to summarise your approach here in terms that mathematicians might find easier to follow.  Please set me straight if I’ve got anything wrong!

I believe that in each case you have identified a subgroup of the automorphism group of the permutation graph that preserves the initial kernel as a set.  An automorphism of the permutation graph is a way of mapping every vertex to another vertex in a manner such that all edges and their weights are preserved under the map.  These automorphisms form a group.  I believe that for n=6 you have identified a subgroup H_4 with 4 elements (including the identity) such that any element when acting on the initial kernel yields permutations that again lie in the initial kernel.  Similarly, for n=7 you have identified a subgroup H_5 with 5 elements that again preserves the initial kernel.

Given that the subgroup H preserves the kernel, if you take any extension E that you could add to the kernel, you can take the orbit of that extension under H:  the result of applying each element of H to E, to get a total of 4 or 5 extensions instead of just one.  (The simplest thing would be to only do this when the extensions in the orbit / aka tuple do not intersect with each other.)

As long as you keep adding 4-tuples or 5-tuples this way, the symmetry of the structure you are building will continue to be maintained, and you can keep adding 4 or 5 extensions at a time.  But evidently the symmetry can only be maintained up to a point:  six 4-tuples in the n=6 case, and twenty-four 5-tuples in the n=7 case.  After that, you’ve completed the structure by adding single extensions.

I hope that’s both accurate in terms of what you’ve done, and clear to other people trying to follow along.

Best wishes

Greg

to Superpermutators

I drew the 2-cycle graph for the superpermutation that Bogdan mentioned upstream in this thread, in his first post to the group.  This uses the first 3-cycle as the initial kernel, and the whole structure attaches to the very first 2-cycle; I haven't drawn the rest of the kernel.

The 2-cycles here are coloured by the orbits they belong to under a 5-element automorphism subgroup that fixes the first 3-cycle as a set. The 139 2-cycles shown (which includes the root from the kernel) comprise 19 cases that belong to no orbit, along with 24 orbits with 5 elements each. Because it isn’t always clear when the 24 hues are distinct, I have also put the orbit number as a subscript to the 2-cycle label.

This graph really surprised me! When Bogdan mentioned that he’d used symmetries to speed up the search, I imagined that he’d started with the kernel and then added 5-tuples (i.e. orbits of 2-cycles under the 5-element automorphism subgroup) for as long as possible, and then only started adding single extensions when he was forced to.  That would have produced a structure with a visible 5-fold symmetry up to a point, with 5 very prominent isomorphic subgraphs.

to Superpermutators

Indeed, I start by first adding 5-tuples for as long as I can, and only after that I start adding single extensions.

to Bogdan Coanda, Superpermutators

to Superpermutators

to Greg Egan, Superpermutators

Thanks for this explanation, Greg. This is really interesting!

Do you have an explicit description of tha 5-element automorphism subgroup used for n=7?

to Greg Egan, Superpermutators

Oh, I get it! In the notation of your diagram, it’s the group generated by the cycle (1 2 3 4 5). Nice and simple.

to Superpermutators

Hi Robin

Right!  And it just cyclically permutes the 2-cycles in the first 3-cycle.

I actually looked at trying to use this to speed up the search last year:

but I was stuck on the notion that the result would be a forest of five strict trees, rooted in each of those five 2-cycles.

In Bogdan’s example, there is some further partial symmetry that I just identified yesterday.

(A) The full stabiliser subgroup of automorphisms that preserve the first 3-cycle as a set of 2-cycles, let’s call it Stab(3), has 10 elements. One order-2 element you can add as a generator to get the full group is (1 2)(3 5) followed by reversal. (The 2-cycle graph has 10,080 automorphisms, with half of them including a reversal.)

Stab(3) is also the stabiliser for a set A of 60 2-cycles in the superpermutation, comprised of half the 120 that come from 5-element orbits.

Under Stab(3), the set A decomposes into 5 orbits of length 10 plus 2 orbits of length 5.

(B) If we call the other 60 of the 120 2-cycles set B, then Stab(B) is another 10-element group, this one generated by (1 2 3 4 5) and (6 7). 

Under Stab(B), the set B decomposes into 6 orbits of length 10.

to Superpermutators

One obvious question to ask might be whether the 20-element subgroup of automorphisms, generated by Stab(3) and Stab(B), plays any role here.

The answer to that seems to be no.  That larger group has orbits of size 10 and 20, and only two of the 10-element orbits lie wholly within the example superpermutation. So that dashes my hope of being able to take chunks of size 20 at a time ... though at least it looks as if, thanks to the two order-10 subgroups, there could conceivably be some benefit in using their orbits to speed up the search.

to Superpermutators

Hi Bogdan

I’ve been trying to recreate your algorithm for myself, and though I have something that’s not too bad  — it can generate the 42,288 solution for n=6 in about 1 minute — I must still be missing something important, because for n=7 it still can’t reach any solutions even when I run it for a day on an iMac, whereas you found 11 solutions in a matter of hours on an iPad!

So if you don’t mind, I’ll sketch what I’m doing, and if it’s not too much trouble maybe you can point to anything that I seem to have wrong?

I start out with a set of initial loops of permutations, consisting of the kernel as a single loop, and all the 1-cycles outside the kernel as their own separate loops of n permutations.

Every loop has a certain number of free edges where it’s possible to join it up with other loops by using an extension.  Each 1-cycle starts out with n free edges.  An edge can either be used, by an extension, or excluded, because of its relationship to an extension:  no two consecutive edges around a 1-cycle can both be used by extensions.

The aim is to add extensions until only one loop remains.  Each extension can join up to n-1 loops together, and in fact every extension that is used must join exactly n-1 of the current loops, or it will be impossible to end up with a single loop after adding the correct number of extensions.

Setting aside the use of n-tuples for a moment, my basic algorithm is:

search():

• Identify a loop L with the smallest number of free edges.  If that number is zero, we're at a dead end with the current state.

• Pick one of the free edges of L, which identifies a unique extension E to add.

• Check whether E is okay to add:

  • Does E join up fewer than n-1 loops?

  • Does adding E exclude an edge that leaves a disconnected 1-cycle with no free edges?

• If E is OK, add it to the solution. This means forming a new loop that contains all the n-1 loops that E visits.  I organise the loops in tree, so this step just involves creating a new parent node in the tree and making the visited loops its children. Whenever I change the free-edge count in a 1-cycle, I propagate the change up the hierarchy of loops that contain it.

• Call search() on the new state with E added.

• Unwind everything we did to add E.

• Then, unless E came from a single free edge in L, exclude E and search() on the state where it is forbidden. (As with adding E, first check whether this excludes an edge that leaves a disconnected 1-cycle with no free edges.)

• Unwind the exclusion.

I know that in your description, you talked about iterating over all the available edges in the loop, but if that was taken literally, wouldn’t it either produce duplicate solutions (if you can choose E_1 at level 1 then E_2 at level 2, and then choose E_2 at level 1 then E_1 at level 2), or miss some solutions (if you exclude all the extensions from the free edges in L, apart from the chosen one, before moving on to the next level, you would miss any solution that used more than one of those edges).

So, I hope that branching between using E and then excluding E is equivalent to what you’re doing. It certainly gives all the 42,288 n=6 solutions, with no duplicates. But maybe there’s something inefficient about this that I’m missing?

To find the loop L with the smallest number of free edges, I just check all the existing top-level loops, which I hold in an unsorted linked list. I did try putting them on a dynamically sorted heap, so that the smallest case would be immediately available, but keeping the heap sorted with all the changes in the free edge counts as extensions are added and removed, then excluded and unexcluded, seemed to take much more time than just finding the smallest entry when it was needed, by checking all the loops.

If you’ve read this far, thank you for your patience!  If you don’t mind, I have one more question, about the use of n-tuples.

There is potentially a clash between the goal of trying to use a complete n-tuple whenever possible (rather than a single extension), and the goal of always adding to the loop with the smallest number of free edges. It might be impossible to add a complete n-tuple that involves any of the loops with X free edges, but possible if you look further to X+1, etc.

The trade-off I chose was to look at all the loops with the same minimum number, X, of free edges, to see if there were any opportunities to add a complete n-tuple, before giving up and adding a single extension.  So I don't look at any loops with more than X free edges, but I if there are multiple loops with X free edges, I do check them all.

Does that make sense to you, or do you have a better strategy?  I found that for n=6, this approach builds all 16 solutions with 6 added n-tuples by actually using the n-tuples, but if I only check a single loop with X free edges, some of those solutions are only reached with some extra individual extensions.

Anyway, thanks again for your patience if you’ve read all this.  I'd be grateful for any comments or suggestions you care to offer!

Best wishes

Greg

to Superpermutators, bogdan...@gmail.com