183 — Tackling the Minimal Superpermutation Problem

A superpermutation of $n$ symbols contains all permutations of those symbols as a substring. For example, the superpermutation of $ABC$ is $ABCABACBA$ because every possible ordering of $A$, $B$, and $C$ can be found in that string.

There’s a really exceptional video about superpermutations on YouTube on the Numberphile channel which really drives home how bizarre it is that we don’t know the minimal length of $superpermutation(6)$.

We know the minimal length of $superpermutation(1)$: It’s just 1. And $superpermutation(2)$ is 3, $superpermutation(3)$ is 9… It was assumed that $superpermutation_{min}(n)=\Sigma_{i=1}^n i!$, but this was only verified for $n\leq5$.

Everything changed when a superpermutation was found for $superpermutation(6)$ of length $(\Sigma_{i=1}^6 i!) - 1$.

And so the search has begun to figure out what the true formula for minimum-length superpermutation strings is. The answer has implications in fields such as DNA sequence alignment, path-finding in graphs, and more.

In fact, Houston shows that this problem is a variant of the Traveling Salesman Problem (TSP), and we can exhaustively solve $superpermutation_{min}(6)$ by traversing a graph of $n!$ nodes, where each represents a permutation of the symbols.

This problem is likely solveable in a few CPU-weeks, but it raises some interesting questions like why does this series diverge from the predicted pattern? What fundamental truth of substrings are we missing in understanding this problem? And, if we can solve $superpermutation_{min}(6)$, is there a way to construct $superpermutation_{min}(n)$ that is smarter than brute force?