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

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

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.

• Which definition of substring are you using? Dec 25, 2010 at 19:35
• @Qiaochu: A substring of a string is a prefix of a suffix of the string Dec 25, 2010 at 22:01
• The length of this string (Minimum length of a string of letters that contains every permutation of n letters as sub-strings, also known as length of the minimal super-permutation.) is known as the A180632 sequence in the OEIS. Although there has been progress since the question was posed (follow the link), not even the exact length is known, let alone a construction. Dec 23, 2018 at 21:20

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.

I would conjecture that the preceding scheme is optimal; the diligent reader can recursively calculate its length.

• It should be $\sum_{k=1}^nk!$. Also, it looks like you can always get a palindrome this way. I still don't have a proof it's optimal, though. Jun 15, 2011 at 19:20
• looks like somebody already conjectured this on the OEIS Jul 1, 2011 at 11:57
• Also here: notatt.com/permutations.pdf Jun 26, 2012 at 15:01
• The conjecture has been disproved. See the arxiv post here. arxiv.org/abs/1408.5108. Oct 4, 2014 at 1:56

I researched this question 20 years ago and found that the length of the shortest string containing all the permutations of n objects to be as stated in http://www.notatt.com/permutations.pdf. We created a computer algorithm to generate all possible strings containing all permutations of n objects and proved this minimal length through brute force for alphabets up to 11 objects. We never could find a proof that our algorithm generated the shortest strings for any n and I would love for someone to pick this subject up. I've found that most mathematicians disregard this topic as already done when in fact, upon close examination, it has not been proven. If anyone knows of such a proof, please pass it along. You can find our paper at Minimal Superpermutations, Ashlock D., and J. Tillotson, Congressus Numerantium 93(1993), 91-98.

• Your conjecture is disproven for n>=6. oeis.org/A007489 arxiv.org/abs/1408.5108 so I wonder how you could have verified it up to n = 11. Did you make some incorrect assumptions? Some simplifying assumptions, some maybe proven not to affect the optimal result, must have been made, since even n = 6 is too large for an exhaustive search. Jan 6, 2019 at 0:12

[NB] This argument as stated is incorrect, and the error is pointed out by Yuval in the comments below. One can indeed use the De Bruijn graph to get all permutations, exactly as I described below, but as Yuval's comment implies, one will also get plenty of non-permutations. The length of the string $S$ is not what my argument says it is, and the problem of the MINIMAL LENGTH sequence seems to require a different argument.

## This is very dangerous because all those undeserved points might cause someone to dismiss what might be an interesting and difficult question.

Since there are $n!$ permutations of $n$ symbols, the string $S$ must have length at least $n!+n-1$. That is, there must be $n!$ starting positions for a permutation, and the last starting position must be succeeded by $n-1$ symbols.

There is in fact such a string, which is obtained from an Eulerian path in the De Bruijn graph $B(n,n)$. This is a directed graph whose vertices are all strings of $n-1$ distinct symbols, with a directed edge from $u$ to $v$ if there is a symbol $s$ such that $v$ has the form $u_1s$, where $u_1$ is $u$ with the left-most symbol deleted. We label the edge with $s$. Every vertex has the same in-degree and out degree so the graph has an eulerian path. The labels of the edges on any such path, together with the string where the path ends, gives a minimal sequence of the kind you want. See this Wikipedia article http://en.wikipedia.org/wiki/De_Bruijn_sequence for terminology, references and a nice explanation.

• Let the alphabet be $\{0,1,2\}$, and suppose that in the string $S$, every subword of length $3$ is a permutation. Wlog, $S$ begins $012$. The next symbol must be $0$, then $1$, then $2$, then again $0$, et cetera. So the sequence cycles only through three distinct permutations out of six. Dec 26, 2010 at 5:53
• De Brujin's sequence is good for representing all words of length $n$, whereas we're interested only in permutations. Dec 26, 2010 at 5:54
• Note however that "universal cycles for permutations" (q.v.) do exist: these use $n+1$ symbols and represent all $n!$ relative orders using a cyclic word of length $n!$. Dec 26, 2010 at 6:05