42
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Which definition of substring are you using? $\endgroup$ – Qiaochu Yuan Dec 25 '10 at 19:35
  • 4
    $\begingroup$ @Qiaochu: A substring of a string is a prefix of a suffix of the string $\endgroup$ – Chao Xu Dec 25 '10 at 22:01
  • $\begingroup$ 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. $\endgroup$ – Bence Mélykúti Dec 23 '18 at 21:20
11
+50
$\begingroup$

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.

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

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Junyan Xu Jan 6 at 0:12
7
$\begingroup$

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

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

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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