The 42,288 superpermutations for n=6 that have the known structure

[Robin Houston]

Hello all!

Since the lower bound is being recalcitrant, I thought it might make a change to have a look at the upper bound again.

I found a way to do a reasonably quick search for superpermutations that have the known structure, i.e. a single 3-cycle with the rest of the 2-cycles attached as a tree.

The idea is to encode it as an exact cover problem, where the elements are 1-cycles and each covering set is a 2-cycle missing a single 1-cycle, and search for solutions using the Dancing Links algorithm popularised by Don Knuth. I assume the tree is rooted at the 3-cycle that begins 123456, and exclude covering sets that intersect this.

Not every solution to the exact cover problem represents a superpermutation of the form we’re looking for, because the partial 2-cycles can make loops, but every superpermutation of the form we’re looking for is a solution of the exact cover problem. So we can enumerate the solutions to the exact cover problem, and discard the solutions that contain loops of partial 2-cycles, to get a comprehensive list of these superpermutations.

Code is here: https://github.com/superpermutators/superperm/blob/master/bin/xc.py

A gzipped file containing all 42,288 of these superpermutations can be downloaded from here: https://github.com/superpermutators/superperm/blob/master/superpermutations/6/872-treelike.txt.gz

I’m currently running with n=7 to see if I can find a superpermutation of this form for n=7. I have no idea whether this is likely to finish within a reasonable time.

Another thing one might try is to adapt the search to look for superpermutations with a different structure, that if they exist would be shorter than 872 characters. It should be possible to rule out many possibilities in this way, though I fear we will need a better understanding of the range of structures that are possible before we can be sure we have exhausted the possibilities and can conclude an actual lower bound, even for n=6.

Best wishes,

Robin

[Greg Egan]

That’s ingenious!

[Tahg]

Well, I knew I was kind of searching for solutions the brute force way, but still surprised you managed to search the whole space that quickly.  I guess I don't need to be running my solver now.  So, we've ended up with 5286 groups of 8; n=5 had 1 group of 6, but hard to say from that what you might expect for n>6.  n=7 has 138 insertions with this structure, and I think that technically means there could be solutions that are symmetrical with themselves.  With n=6, any permutation of the 3-cycle was guaranteed to create a different balance in the tree.

[Robin Houston]

Have you checked that all the superpermutations your solver has found are in this list?

If not, that suggests *something* doesn’t work the way I thought it did, which would be interesting.

--
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/39169cbb-5d43-4e5e-906c-639d4f89880a%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Tahg]

I threw together some code to check this, and it seems that all the solutions I've found are indeed in that list.  All told, I had found about 20% of the solutions in your list with my brute force solver.  I have no doubt it would have come up with the same results given enough time.

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.

[Tahg]

Currently looking to convert solutions back in the format my program finds, and then into structured cycles.  It's a bit difficult to see the structure with just the plain number.

[Robin Houston]

There’s a program in the repo, bin/2cycles.py, which will take a superpermutation and print out the 2-cycles it contains and which others each one overlaps.

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/39169cbb-5d43-4e5e-906c-639d4f89880a%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

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/ddb15696-fe7c-48fe-b0a2-4e94d60b81be%40googlegroups.com.

[Tahg]

Ok, managed to find an online interpreter to run that code.  I think I understand it, but it's hard to visualize the tree from the way that is printed.  The way I was doing it started with the initial 3-cycle as 4 2-cycle roots.  Each additional partial 2-cycle is fully enclosed within an existing 2-cycle, creating a "branch".  In addition, I was displaying cycles based on their initial element, rather than rotating to a canonical form.  It's of course not hard to go from one to the other, you start with 6 12345, 6 15234, 6 12534, 6 12354, and then recursively add the neighbors until you get the tree.

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.

To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/39169cbb-5d43-4e5e-906c-639d4f89880a%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

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

[Tahg]

Nested structure of all the solutions. I found it interesting that there's seemingly no order to them.