Introduction: Efficient O((n−1)!) implementation for Superpermutation research

[yusheng hu]

Hi Superpermutators group,

I am an independent developer and algorithm enthusiast from China. I'm excited to join this community!

I’ve been developing an efficient C++ implementation of the Ring Cascade Permutation Algorithm (O((n−1)!)). The algorithm draws inspiration from superpermutation generation logic; interestingly, the full permutations it generates can be combined to align exactly with the known upper bound of superpermutations.

I have successfully verified the implementation up to n=15 (totaling 1,401,602,636,313 ).

Project Link: https://github.com/Yusheng-Hu/Ring-Cascade-Permutation-Algorithm

I would be honored to have you experts review my code or utilize it in your search for shorter superpermutations. 

Best regards,

Yusheng HU

2026-04-29

[Ranbir Das]

Hello

Interesting work Yusheng! ! Going through it. 

Thanks for sharing 

--
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/991b0acf-1136-4c11-bb4f-90726f3d5fb1n%40googlegroups.com.

[Miles Gould]

Hi Yusheng,

I note that your README and paper claim

Optimal Superpermutation: Provides a universal constructive proof for the Superpermutation problem, yielding sequences that strictly attain the theoretical lower bound L = \sum_{i=1}^n i!

But this is not the best known lower bound! That's the length of the superpermutation constructed by the recursive algorithm, but we've known for a while that the recursive algorithm is not optimal for n > 5: indeed, that's how this whole project got started! So actually this is not even a lower bound for the length of the optimal superpermutation, it's an upper bound, and it's also not the best known upper bound. For n > 6 it's beaten by the Egan-Williams algorithm, and for n = 6 or 7 we also have even shorter superpermutations found by custom search code.

[I also constantly get lower and upper bounds mixed up when thinking about this problem, by the way!]

I've created a spreadsheet showing the various known bounds up to n=15 at Superpermutation bounds - Google Sheets. By the way, does anyone know how to get Google Sheets to handle very large numbers? The proposed Hunter lower bound doesn't actually go below zero at n=14, that's just integer overflow.

Anyway, it sounds like you've found a faster algorithm equivalent to the recursive construction, which is still interesting. I look forward to reading your paper!

Best regards,

Miles

[Clarence]

I do not think the algorithm can really run in O((n-1)!) time. The amount of time taken should be lower bounded by the output length.

[Miles Gould]

Oh, good point. Outputting n! permutations of length n should be at least O(n.n!). If I'm reading this Reddit thread correctly, the algorithm produces the permutations in-place, so you could perhaps achieve O(n!) if advancing to the next permutation only required a constant number of swaps (I think the 4chan algorithm might work like this?). But I see a lot of memcpy calls in the code, so maybe not.

To view this discussion, visit https://groups.google.com/d/msgid/superpermutators/ad189d6a-d7b2-465d-af16-8cfea2cd496an%40googlegroups.com.

[yusheng hu]

https://papers.ssrn.com/sol3/papers.cfm?abstract_id=6553539

The preprint is approved today. pls help to discuss.

Miles Gould <mi...@assyrian.org.uk> 于2026年4月29日周三 21:46写道：

To view this discussion, visit https://groups.google.com/d/msgid/superpermutators/CAKFNCm3XHOcRN-9QyNz1GuLogiKLn1y-ssv8WqeLce2aC0059g%40mail.gmail.com.

[Clarence]

According to my understanding:
- To generate all permutations of 0 to n-1, first generate all permutations 2 shorter (of length 0 to n-3), then form a string of length ~3n that you can (O(1)-cost) modify ~n times to have all the permutations generated at some point as contiguous memory. This makes a total of O((n-1)!) cost of memory operations. If one uses it to iterate through the permutations, it would still take O(n!) time.
- I think there's some idea of an advantage that can be obtained by parallel computing, that the different permutations can be read at the same time. Big-O-wise it is probably not very significant, one can rather easily partition the set of permutations (for instance by fixing the first element).

- At the moment I'm not familiar enough with the current research in superpermutations as to where this can be applied.

[Miles Gould]

I've now read the paper, and from Figure 1 it's clear that this is exactly the recursive algorithm (though perhaps a more memory-efficient implementation of it), so it's not at all surprising that it produces superpermutations of the same length. Which, again, is not optimal for n > 5. The claim in section 5.3 that it "maintains a constant n-1 overlap at every transition" is simply incorrect, as can be seen from the bottom row of Figure 1. The bit in section 5.2 about generating any given permutation in O(n) time is interesting, but I don't think that's a new capability? And, as previously discussed, I don't think O((n-1)!) time complexity is even possible for this problem since you must enumerate O(n!) objects.

Sorry, dude.

To view this discussion, visit https://groups.google.com/d/msgid/superpermutators/CAN7%3DkSmnv2W15WsDMj8pRH2jFBVef6PRgkVYLmwY%3DzDt80LiPw%40mail.gmail.com.

[yusheng hu]

Thanks miles.

Point 1: On Superpermutation Length
The algorithm's output length strictly follows the ∑i=1n​i! formula, I acknowledge this is not the absolute lowest bound.  

Point 2: On Computational Complexity
The complexity claim focuses on the internal construction within memory rather than the physical output process. If the task is defined as explicit enumeration or output, the complexity is inevitably O(n!) or O(n*n!).  

Point 3: On Batch Generation(This is new)
A single shift in memory simultaneously generates n new permutations. Specifically, we use an O(n) operation to generate n×(n−1) new permutations in memory, resulting in an amortized cost of approximately 1/n per permutation.

[yusheng hu]

Thank you for taking the time, your understanding is very accurate. If we enumerate each result, the complexity still needs to be amplified to n!. But from the perspective of building results, it can already be evenly divided into less than one instruction. This result takes into account all costs, and the RCPA algorithm is still faster than any current full permutation generation algorithm, making the generation algorithm as cost free as assignment.
For the method of fixing the head, the efficiency will be lower.
From a purely technical perspective, we have achieved a construction complexity that is less than the complexity of the output result.
Algorithms have the benefits of parallelism and randomness.
I also don't know what use it is for super permutation. Quick construction?

[Miles Gould]

OK, so you're saying that your algorithm has O((n-1)!) time complexity because you're processing n permutations in parallel?

To view this discussion, visit https://groups.google.com/d/msgid/superpermutators/de63c83b-62a1-4799-a8f7-a325665d5a2dn%40googlegroups.com.

[Ranbir Das]

Good Morning

Does one have to frame the value around super permutation length - what about it's use as a means of efficient traversal of permutation space ?  That seems like it can show up in exhaustive testing, structured search, and any setting where overlap reduces recomputation. A faster construction method could be useful there, even if it doesn’t change the known bounds.  

Thanks

To view this discussion, visit https://groups.google.com/d/msgid/superpermutators/3dd4983f-bb34-4364-908c-4c50edfdd488n%40googlegroups.com.

[yusheng hu]

Parallelism doesn't mean multiple cores running in parallel. The algorithm's execution logic is that a single shift operation simultaneously generates n new permutations in memory. If you also pay attention to the amortization logic, when processing layers n-2 and n-1, only n-1 actions are consumed.