n=7 superpermutation of length 5905

[Andrei Teodorescu]

Hello all,

I have used https://github.com/superpermutators/superperm/blob/master/PermutationChains/PermutationChains.c (with no symmetry flags) with the kernel 4666446666-6666466636666-666646646666-666646646666-6666366646666-6666446664 (obtained using KernelFinder.c) and I think I have found 4 length 5905 superpermutations for n=7.

Best regards,

Andrei

[Shea Street]

I am currently away from my typical workstation but ran checks that I could. I typically want to double check not using AI especially just on my phone but it looks like these check out for counts and some shared common structuring. Thanks for sharing! I will make sure to reverify closer when I can.

--
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 view this discussion, visit https://groups.google.com/d/msgid/superpermutators/fc74cc0f-4644-41b6-b12e-03c70b6cbc3an%40googlegroups.com.

[Andrew Balint]

I validated that each word is a complete n=7 superpermutation of length 5905, covering all 5040 permutations. However sol3 = reverse(sol1) with symbols 3 and 4 swapped, and likewise sol4 = reverse(sol2), also with 3 and 4 swapped. Reversal and relabeling both preserve validity, so only two of these words are unique. Still an awesome find, congrats on the discovery

[Ranbir Das]

Dear All

Thank you for sharing the codebase, going through it. 

Regards

To view this discussion, visit https://groups.google.com/d/msgid/superpermutators/ef60f555-a7b5-445a-8dec-0a5545bad0dcn%40googlegroups.com.

[Ranbir Das]

Respected All

Thank You for sharing the codebase to go through. 

On a note related to Agentic Systems - I am currently collecting a questionnaire from interested teams for their transparent usage of A.I. applications - in this regard after my SLR for our university (AdtU), this is an initial form we are proposing to use : Sectors of Generative A.I. - Research Study

Inputs for the same will be highly appreciated, including related correspondence. 

Best Regards 

[Robin Houston]

Very cool! Can you say something about how you selected that kernel?

Robin

[Miles Gould]

Added to the spreadsheet - congratulations! Can we lift this to shorter superpermutations for higher n?

Miles 

[Andrei Teodorescu]

On Tuesday, 18 August 2026 at 11:54:55 UTC+2 robin....@gmail.com wrote:

Very cool! Can you say something about how you selected that kernel?

I have tried many kernels before getting to that one.

Longer version:

In the last month I have tried many kernels (millions) generated using KernelFinder.c, most of the time on AWS small/medium instances with occasional upgrades to 4-8-core C-series to speed things up.

About a month ago I tested length 29-81 palindromic kernels using symmPairs+fullSymm but didn't find any solution (there are about 20M of them and almost all fail immediately).

But I was convinced that if a solution existed it would be generated by a short non-palindromic kernel (maximum flexibility, for example 66646646664466646662666466466646666 and 6664666466646666-6666466466646666) so I tried (together with Antigravity and Claude) some ideas to improve the speed of the search:

Most of the ideas were unsuccessful:

- meet in the middle, splitting the search graph into independent parts, stitching partial results together, caching remaining 2-cycles, investigating if some tested configurations are isomorphic - nothing helped

- modeling restrictions as a SAT problem. With the modelling I (and the agents) tried a SAT result didn't mean solvable and an UNSAT result generally came too late in the search (when it was already cheaper to let the backtracking complete unsuccessfully on that branch)

What worked was a counter-intuitive heuristic that brought up to 100X speed improvements for kernel lengths 31-40:

- AI summary: "At each node, searchPC() collects every top-level loop tied for the smallest freeCount into minL[], then branches on the first of those for which traverseLoopSearch() succeeds. Since that call succeeds for the first candidate in essentially all cases, the branching loop is the one that appears first in nextTop list order, and the remaining tied candidates are not consulted. h5 replaces that selection with an explicit comparison among the tied candidates.
Why the selection matters. The branching factor at a branch node is exactly 2, and the large majority of nodes are forced moves rather than branches. The shape of the entire subtree is therefore determined by which of the tied loops is branched on, making this single choice the dominant structural lever in the search.
The rule. For each loop tied for the minimum freeCount, consider its two candidate 2-cycles, and for each 1-cycle those 2-cycles touch, take that 1-cycle's currentTop->freeCount. Sum these to score the loop, and branch on the loop with the highest score — that is, the one whose immediate options retain the most free capacity in the surrounding structure."

(The usual fail-first intuition - branching where the problem is most constrained - didn't work well here)

Noticing that the search on longer kernels was faster than the search on shorter ones (because of the extra restrictions) I went back to the list of long palindromic kernels, tested them without symmetry parameters and found the above solution.

I am running KernelFinder to search for 5904 superpermutations in the same solution space (large palindromic kernels but without symmPairs+fullSymm) but with no luck so far.

Andrei

[Randy Olsen]

This new result invalidates my prediction scheme going back to 2020, I must admit. Congratulations Andrei Teodorescu for pushing on this problem and finding a new record. Thanks for the background and explanation you added. -Randy Olsen

[Miles Gould]

Cool! Could you open a PR adding your speedups to the kernel search code?

[I see we currently have seven open PRs on the superperm repo, mostly dating back to 2019. We should probably do something about that. Two of them are mine, both still in draft mode...]

Miles

To view this discussion, visit https://groups.google.com/d/msgid/superpermutators/e77b848d-3e99-4df6-a405-3995ef551082n%40googlegroups.com.

[Robin Houston]

Perhaps you're already trying this, but just in case – some recent superpermutations posted here have had repeated permutations in their kernel; or, to put it a different way, have had kernels that use weight-3 edges that are not the standard prefix-reversal edges we've mainly been relying on.

So that suggests it may be fruitful to widen the class of kernels under consideration.

Robin

On Tue, 18 Aug 2026 at 16:00, Andrei Teodorescu <spag...@gmail.com> wrote:

To view this discussion, visit https://groups.google.com/d/msgid/superpermutators/e77b848d-3e99-4df6-a405-3995ef551082n%40googlegroups.com.

[Andrei Teodorescu]

I haven't tried searching for superpermutations with repeated permutations but for n=7 it seems that the kernel-based approach is reaching its limits. If my scrips are correct I have tried all kernels up to length 51 (palindromic up to 90), the count of kernels is much lower at score 20 (hundreds of thousands) compared to score 15 (millions) and all of them immediately exit the search (too many constraints). The open question, as mentioned by others in the past, is whether a superpermutation of a certain (minimal) length containing duplicates exists when one without duplicates doesn't.

I have created a PR for the search improvement (useful for n = 7 for score 10 and score 15 searches that visit many nodes), thank you Robin Houston for the fast approval.

Regarding lifting the newly found superpermutation to higher n maybe someone with more experience can jump in and help. My understanding from the previous discussion was that the method was specific to that class of superpermutations (maintaining a single character gain) and not immediately applicable to any other kernel.

[Andrei Teodorescu]

Here are some transformed versions of the first two solutions, keeping the same length (5905) but creating repeated permutations by moving a block of 7 characters to a different position.

I have also attached two AI-generated versions where the transformations were chained to create 4 repetitions.

The transformations are very similar between the first and second solution (same repetitions on the same positions) because the two solutions share the same kernel.

Sample output from my verification runs:

Analyzing File: sol1_5905_dup_chain4.txt

Permutation [1243567] appeared 2 times at indices: [204, 211], Permutation [1265437] appeared 2 times at indices: [5515, 5522], Permutation [7435621] appeared 2 times at indices: [376, 383], Permutation [7654321] appeared 2 times at indices: [5687, 5694]

Andrei