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

I thought of this problem while reading a open problem on shortest supersequence of all permutations.

  • Which definition of substring are you using? – Qiaochu Yuan Dec 25 '10 at 19:35
  • 4
    @Qiaochu: A substring of a string is a prefix of a suffix of the string – Chao Xu Dec 25 '10 at 22:01

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. – A. De Luca Jun 15 '11 at 19:20
  • 1
    looks like somebody already conjectured this on the OEIS – A. De Luca Jul 1 '11 at 11:57
  • 1
    Also here: notatt.com/permutations.pdf – leonbloy Jun 26 '12 at 15:01
  • 7
    The conjecture has been disproved. See the arxiv post here. arxiv.org/abs/1408.5108. – Chao Xu Oct 4 '14 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.

[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.

  • See also this question: math.stackexchange.com/q/13358/1242. – Hans Lundmark Dec 25 '10 at 22:33
  • The graph we want isn't a de Brujin graph, is it? That graph has too many vertices. – Qiaochu Yuan Dec 26 '10 at 4:56
  • 1
    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. – Yuval Filmus Dec 26 '10 at 5:53
  • 2
    De Brujin's sequence is good for representing all words of length $n$, whereas we're interested only in permutations. – Yuval Filmus Dec 26 '10 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!$. – Yuval Filmus Dec 26 '10 at 6:05

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.