# What is the shortest string that contains all permutations of an alphabet?

What is the shortest string $$SS$$ over an alphabet of size $$nn$$, such that every permutation of the alphabet is a substring of $$SS$$?

Edit 2019-10-17:
This is called a superpermutation, and there is a wikipedia page that keeps track of the best results. Turns out the problem is still open.

Here are some thoughts: given a permutation $abcde$, you can generate all its cyclic rotations with no additional cost: $abcdeabcd$. Then you’d want to capitalize of the largest number symbols, so we repeat the deepest symbol, in this case $a$, complete the permutation with $e$, and generate all cyclic rotations: $abcdeabcdaebcda$. So far we’ve generated all cyclic rotations of $abcde$ and $bcdae$. Notice that the first $n-1$ characters are rotated. We continue to generate all cyclic rotations of $cdabe,dabce$, and then we have to bring back one symbol shallower: $\ldots dabcedabcadebcad$. So we moved from $dabce$ to $bcade$. This corresponds to rotation of the middle $n-2$ characters, followed by the usual rotation of $n-1$ characters. Now we get back to the earlier operation (rotation of $n-1$), applying occasionally the new rotation, until we get stuck; we would then need to do a rotation of the middle $n-3$ characters, and so on.