**365**Papers

# 183 — Tackling the Minimal Superpermutation Problem

Read on 19 February 2018A 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?