New record superpermutation for n=7

[Robin Houston]

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.

[Robin Houston]

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

[Justin Hoffman]

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)

What is the difference between the dotted lines and the solid lines?

What determines if a node has 1 child vs many? (Maybe this is explained by the notation.)

[Niles Johnson]

I'm excited to see the recent progress -- great work all :)

On Fri, Feb 1, 2019 at 11:44 AM Justin Hoffman <jstn...@gmail.com> wrote:

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)

I don't know if it's findable by search, but Greg Egan has written about this here:

http://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html

 

What is the difference between the dotted lines and the solid lines?

What determines if a node has 1 child vs many? (Maybe this is explained by the notation.)

I've fallen behind a bit, so I don't know how to answer these questions, but they might be answered on Egan's writeup.

-Niles

 

--
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/56583751-6602-4f9b-9066-f78a39f54f53%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Robin Houston]

Good questions, thanks for asking!

There’s a discussion of 2-cycle graphs on Greg Egan’s page: http://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html#TCG

(He writes 4|123 where I write 4/123. IIRC he and I invented these very similar notations independently and simultaneously; I’ve stuck with the slash because I find it harder to confuse with a 1 when I’m writing by hand.)

In short, 4/123 is the 2-cycle that consists of all the permutations that are made from some rotation of 123, with a 4 inserted anywhere. For example, the permutation 2341 belongs to 4/123, because 231 is a rotation of 123.

A solid line means that the two 2-cycles share a 1-cycle. The dashed lines mean that the two 2-cycles are neighbours in a 3-cycle. The dotted lines mean they’re neighbours in a 4-cycle.

So the long dashed-and-dotted line from 7/123456 at the bottom-right to 7/123564 at the top-left is the principal 4-cycle, i.e. the 4-cycle that begins 1234567.

--

[Tahg]

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

On Friday, February 1, 2019 at 11:53:37 AM UTC-5, Robin Houston wrote:

Good questions, thanks for asking!

There’s a discussion of 2-cycle graphs on Greg Egan’s page: http://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html#TCG

(He writes 4|123 where I write 4/123. IIRC he and I invented these very similar notations independently and simultaneously; I’ve stuck with the slash because I find it harder to confuse with a 1 when I’m writing by hand.)

In short, 4/123 is the 2-cycle that consists of all the permutations that are made from some rotation of 123, with a 4 inserted anywhere. For example, the permutation 2341 belongs to 4/123, because 231 is a rotation of 123.

A solid line means that the two 2-cycles share a 1-cycle. The dashed lines mean that the two 2-cycles are neighbours in a 3-cycle. The dotted lines mean they’re neighbours in a 4-cycle.

So the long dashed-and-dotted line from 7/123456 at the bottom-right to 7/123564 at the top-left is the principal 4-cycle, i.e. the 4-cycle that begins 1234567.

On Fri, 1 Feb 2019 at 16:44 Justin Hoffman <jstn...@gmail.com> wrote:

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)

What is the difference between the dotted lines and the solid lines?

What determines if a node has 1 child vs many? (Maybe this is explained by the notation.)

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

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.

       3245167                            

       2451673                            

       4516732                            

       5167324                            

       1673245                            

   +++ 7324561                            

       3245617                            

       2456173                            

       4561732                            

       5617324                            

       6173245                            

       1732456                            

   +++ 3245671                            

       2456713                            

       4567132                            

       5671324                            

       6713245                            

       7132456                            

       1324567                            

   +++ 2456731                            

       4567312                            

       5673124                            

       6731245                            

       7312456                            

       3124567                            

       1245673                            

   +++ 4567321       4567321       4567321

       5673214       5673214       5673214

       6732145       6732145       6732145

                 +++ 3214576              

                     2145763              

                     1457632              

                     4576321              

                     5763214              

                     7632145              

                     6321457              

                 +++ 2145736              

                     1457362              

                     4573621              

                     5736214              

                     7362145              

                     3621457              

                     6214573              

                 +++ 1457326              

                     4573261              

                     5732614              

                     7326145              

                     3261457              

                     2614573              

                     6145732              

                 +++ 4573216              

                     5732164              

                     7321645              

                     3216457              

                     2164573              

                     1645732              

                     6457321              

                 +++ 5732146              

                     7321465              

                     3214657              

                     2146573              

                     1465732              

                     4657321              

                     6573214              

       7321456   +++ 7321456       7321456

       3214567       3214567       3214567

                               +++ 1456723

                                   4567231

                                   5672314

                                   6723145

                                   7231456

                                   2314567

                                   3145672

                               +++ 4567213

                                   5672134

                                   6721345

                                   7213456

                                   2134567

                                   1345672

                                   3456721

                               +++ 5672143

                                   6721435

                                   7214356

                                   2143567

                                   1435672

                                   4356721

                                   3567214

                               +++ 6721453

                                   7214536

                                   2145367

                                   1453672

                                   4536721

                                   5367214

                                   3672145

                               +++ 7214563

                                   2145637

                                   1456372

                                   4563721

                                   5637214

                                   6372145

                                   3721456

       2145673       2145673   +++ 2145673

       1456732       1456732       1456732

   +++ 5673241                            

       6732415                            

       7324156                            

       3241567                            

       2415673                            

       4156732                            

       1567324                            

   +++ 6732451                            

       7324516                            

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

Best wishes,

Robin

[Robin Houston]

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

[Greg Egan]

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:

n = 7, with 5907 digits, discovered by Charlie Vane

[Bogdan Coanda]

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]

I made a little spreadsheet for the lower bound I'm getting based on the above 'kernel' + 'extensions' approach

Z = (n³-2n²+n-3) + (n²-n-1) * (n-1) * ((n-3)! - 1)

https://docs.google.com/spreadsheets/d/1hkh7BW6eOp8-y-eVPSO5jqF7fkzwO11LD8UtKi_mEJA/edit?usp=sharing

[Jay Pantone]

Hi Bodgan,

This is fantastic! Thanks for your explanation. 

Inspired by this n=7 superpermutation, Vince Vatter, John Engbers, and I did a few calculations yesterday. We noticed, too, that it consisted of the initial 4-loop, with the weight-1 edge 3416752 -> 4167523 broken apart. Instead a weight-2 step is taken from 3416752 -> 1675243, then an Egan-style walk is done on all permutations not in the initial 4-loop (which is 5/6 of the permutations in S_7). The walk ends at just the right place 3241675, to lead to 4167523 upon a weight-2 step. Then, the initial 4-loop is finished.

We wondered what such a construction could achieve for arbitrary n, starting with an initial k loop (for any k). Knowing that Egan's construction is best possible given its restrictions (from our pdf a while back), the best this construction can do is precisely:

  n! + (n-1)! + (n-2)! + (n-3)! + (n-4),

one less than Egan's construction, and this is exactly when k=3 or k=4.

We see this construction as an optimized interpolation between:

 - the recursive construction, which has big steps, but visits few 2-loops,

 - Egan's construction, which has small steps, but visits many 2-loops.

The question remains whether there is always a weight-1 step you can break and an Egan-style walk you can insert (which ends at the right place). We still have hope that we can improve the algorithm to construct these walks!

All the best,

Jay

--

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/63876a03-0f19-42d7-83c7-ffa959e5a58c%40googlegroups.com.

[Greg Egan]

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

[Greg Egan]

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.

[Tahg]

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.

[Greg Egan]

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?

[Bogdan Coanda]

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)

054123 ⇐ 320541 // (walking backward)

301452 ⇒ 145203 // (walking forward)

254301 ⇐ 102543 // (walking backward)

and we arrive at:

'Walking' a 1-link (L1) from here means: 

345021 ⇒ 450213 // (walking forward)

320541 ⇐ 132054 // (walking backward)

145203 ⇒ 452031 // (walking forward)

102543 ⇐ 310254 // (walking backward)

and we arrive at:

'Walking' another 1-link (L1):

and now we 'extend' from these 4 points we arrived at, keeping in mind that for two of them we have the 'end' node:

we walk a little more, L2 L1 L1 L1:

we 'extend' again from all 4 nodes we currently have:

we define a 'jump' as a sequence of (L1 L1 L1 L1 L1 L2)

and we 'walk' L2 jump jump L1 L1 L1:

extend:

walk L1 L1 L2 L1:

extend:

walk L2 jump jump jump L1 L1 L1:

extend, of course:

walk another L2 L1 L1 L1:

extend for the 6th and last time:

and now we have the common set of 24 extensions between the four solutions I started this post with - but found in 6 iterations.

This is basically what I did for #7, but with 5 starting points, and all going in the same direction instead of sideways

kernel: 012345601234506123450162345012634501236450123465012340561234051623405126340512364051234605123406512340156234015263401523640152346015234061523401652340125634012536401253460125340612534016253401265340123564012354601235406123540162354012635401236540123

[Bogdan Coanda]

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:

Take #6, completely unconnected:

// off-topic: the colored numbers between nodes are loop (2-cycle) unique identifiers - each one appears 5 times, at the points where it connects to each of 5 1-cycles

now, let's connect all nodes through 1-links:

we now have 120 disjoint chains, with a theoretical cost of 720 (and a ratio of 1), and we are visibly forced to use (at least) 2-links to further connect the graph.

if we now use a 2-link, we have to disconnect two corresponding 1-links: 

And we end up with 118 closed chains, and one path with the only two open ends we are permitted... 

Thus, anything else we are going to do to this graph has to close back on itself to maintain the two open ends max limit, and so we are forced into applying only full 2-chains (the extensions I keep naming - we could do 3-chains and more, but the lowest ratio is for 2-chains - 29 added length per 24 added nodes = 1.208..) 

Or, we can maintain the closed status from the beginning, only applying 2-chains to further connect the graph (starting from the 120 connected cycles in the second image above), and only removing the costliest edge at the end to obtain a path from the single closed chain we 'should' have.

But, consider the following: 

- every applied extension to the above connects 5 chains together into one

⇒ thus decreasing the total number of chains by 4, and upping the graph cost by 5

- and we are starting with the 120 chains above

⇒ so we can only decrease down to 4 remaining chains by just applying extensions

- let's say we can connect these 4 chains through one last partial extension, meaning we remove four 1-links and add three corresponding 2-links // first method

⇒ this is the same as starting from a path (kernel) built from four 1-cycles connected by three 2-links, and adding 29 extensions to it // second method

⇒ the total cost for this construct is 

873 = 6*120*[1] + 29*[5] + 6 /*start perm*/ - 4*[1] + 3*[2] // by the first method

= 5*4*[1] + 3*[2] + 6 /*start perm*/ + 29*[29] // by the second method

So, in my point of view, this always boils down to what kernel to start adding extensions to.

I drew another table or two: https://docs.google.com/spreadsheets/d/1rYXMjVBV3SI_KylCikTtP1sCinKbgNZM5I33Xwr9xLY/edit?usp=sharing

[Greg Egan]

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

[Greg Egan]

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.

But this structure starts with a single symmetry-breaking extension, and then the various elements of the first orbits added are not initially connected to the existing graph.

So I guess that means the algorithm didn’t build a connected graph in stages, and worked more like Robin Houston’s exact cover approach?

[Bogdan Coanda]

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

I start with all nodes connected in 1-cycles (except for the kernel I pre-build into the map)

For #7 this results in all 5040 permutations grouped into 690 1-cycles and 1 kernel (691 closed chains in total)

- each possible extension connects 6 such closed chains into a single chain, still closed.

- a tuple step thus connects 30 chains into 5

- once I have a single closed chain remaining, I remove the costliest edge (the 3-link from the initial kernel that kept it a closed chain)

You may notice that a viable solution needs to have all of the initial 1-cycles connected by at least one extension to the rest of the chain, so the availability to be further connected is one of the top-most things I keep track of in my algorithm:

at every step, I check:

- if all 1-cycles (actually all current chains) have at least one node each with an 'available' extension that allows them to be connected in a subsequent step in the backtracker

=> if any chain has a single 'available' connection, I extend that one on the next step, being forced into it.

basically:

def back():
  if len(diagram.chains) == 0:
    => found a solution
  else:
    selected_chain = find chain with smallest number of available extensions
    if len(selected_chain.available_extensions) == 0:
      return

    for each available extension: # (will be between 0 and N)
      extend the tuple containing this individual extension # (or just this extension if we're done with tuples)
      back()
      collapse back the tuple extensions

[Robin Houston]

Hi Bogdan,

Thank you so much for your great explanations. It’s a clever idea, and wonderful that it works so well.

I suspect you have already realised this, but in case it’s of interest to you or anyone else, your formula

(n³-2n²+n-3) + (n²-n-1) * (n-1) * ((n-3)! - 1)

is equal to n! + (n-1)! + (n-2)! + (n-3)! + (n-4), which is the form we’ve been writing it in. Here’s the calculation:

--
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/769d8c6d-47eb-42b4-8468-a7028a97a4b9%40googlegroups.com.

[Bogdan Coanda]

yep, you're right - /facepalm - I just checked my spreadsheed and I had mistyped a digit… nice derivation :)

[Robin Houston]

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?

Robin

--
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/41092f4a-0ae2-430d-b937-dc99efb13e85%40googlegroups.com.

[Robin Houston]

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.

[Greg Egan]

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:

https://groups.google.com/d/msg/superpermutators/cwtSZvEX1iY/gTyivEzkCAAJ

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.

[Greg Egan]

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.

[Greg Egan]

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

[Greg Egan]

Hi

I just added a new section to my algorithm, so that every time it builds a new loop, it goes through the loop and identifies all the extensions that might be applied to it. If any of these extensions make contact with the loop in more than two locations, they are immediately excluded.

This small trick seems to have made a big difference:  finding the 42,288 n=6 solutions went from 60 seconds to 20 seconds, and the algorithm produced a couple of n=7 solutions (for the larger kernel, aka the 4-cycle) after 20 minutes.  I don't use any kind of n-tuple for that kernel.

I'm still waiting to see if this change has been enough to yield any solutions for the smaller kernel, the 3-cycle, in a reasonable time.

And it would still be great to hear anything Bogdan wants to say about his own optimisations.  I bet I'm still missing some trick that could help even more.

Best wishes

Greg

--

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/b6f3a3ab-6a93-4105-b512-31b36bcbe369%40googlegroups.com.