An attempt to find an optimal heuristic solution to the superpermutation problem.
This repo is where I play around with the superpermutation problem, which is still an open problem in math. It's a mix of my own explorations and other people's algorithms and solutions, implemented here so I can compare them side by side.
The standard strategy is the classic recursive construction with length 1! + 2! + ... + n!.
It stops matching the shortest known superpermutation once the alphabet has 6 symbols.
The egan strategy is Greg Egan's construction with length n! + (n-1)! + (n-2)! + (n-3)! + n - 3.
It beats standard once the alphabet has 7 symbols.
The pantone strategy is Jay Pantone's construction from his 43/80 upper bound work, which builds on Egan's.
It uses his computer-found seeds, so it hits his Lean-proved length of 46,181 for 8 symbols.
For 9 symbols it also uses the cut points and join order from rumstd's tweak of Pantone's word, which gets it down to 408,731.
For fewer than 8 symbols it falls back to whichever of standard and egan is shorter.
The euler strategy is my own take on Pantone's construction.
Instead of using his precomputed seeds, it searches for its own seed every time you run it, looking for a walk through the 2-loops that stays the same when you swap certain pairs of letters.
For 8 symbols it finds a seed just as good as Pantone's, so it hits 46,181 without any outside data.
No seed with that kind of symmetry does better, so beating 46,181 this way would take a seed without it.
For 9 symbols it carries that seed up one size, which gets 408,831.
For fewer than 8 symbols it falls back to whichever of standard and egan is shorter.
The shortest column is the shortest length I know of for each alphabet size, collected from other people's work (see the links at the bottom).
| |alphabet| | |shortest(alphabet)| | |standard(alphabet)| | |egan(alphabet)| | |pantone(alphabet)| | |euler(alphabet)| |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 3 | 3 | 3 | 3 |
| 3 | 9 | 9 | 9 | 9 | 9 |
| 4 | 33 | 33 | 34 | 33 | 33 |
| 5 | 153 | 153 | 154 | 153 | 153 |
| 6 | 872 | 873 | 873 | 873 | 873 |
| 7 | 5907 | 5913 | 5908 | 5908 | 5908 |
| 8 | 46181 | 46233 | 46205 | 46181 | 46181 |
| 9 | 408731 | 409113 | 408966 | 408731 | 408831 |
Here's an example of each command along with what it prints. Color is turned off so the output reads cleanly here.
Generate a superpermutation with the egan strategy
$ superperm generate ABCD -s egan
ABCDACBDCABDCBADCBDACDBACDABCADBCAGenerate every variant of a superpermutation that has the same shape
$ superperm perms ABC | xargs -n1 superperm generate
ABCABACBA
ACBACABCA
BACBABCAB
BCABCBACB
CABCACBAC
CBACBCABCList every permutation of an alphabet
$ superperm perms ABC
ABC
ACB
BAC
BCA
CAB
CBARelabel an existing solution into every variant with the same shape
$ superperm perms ABC | xargs -n1 superperm translate ./solutions/shortest/3-9.txt
ABCABACBA
ACBACABCA
BACBABCAB
BCABCBACB
CABCACBAC
CBACBCABCCheck that a solution contains every permutation
$ superperm verify ./solutions/shortest/3-9.txt
valid superpermutation for n=3 with alphabet ABC and length 9See where each permutation shows up in a solution
$ superperm analyze extract --no-color ./solutions/shortest/3-9.txt
ABC
BCA
CAB
BAC
ACB
CBACount how many permutations each character is part of
$ superperm analyze heatmap --no-color ./solutions/shortest/3-9.txt
A B C A B A C B A
1 2 3 2 2 2 3 2 1
♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦
♦ ♦ ♦ ♦ ♦ ♦ ♦
♦ ♦ Rearrange a solution's cycles and watch the layout change
$ superperm analyze interact ./solutions/shortest/3-9.txt
ABC
BCA
CAB
BAC
ACB
CBA
length 9 · ←/→ select · ↑/↓ move · r/R rotate elements · s/S rotate cycles · q quitPlot each character's position in the alphabet
$ superperm analyze position --no-color ./solutions/shortest/3-9.txt
A B C A B A C B A
♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦
♦ ♦ ♦ ♦ ♦
♦ ♦ Run make help for all available commands. In general, you can run make build-all to build the binary for all platforms.