22
$\begingroup$

Given an alphabet with $n$ characters, what is the shortest sequence that contains all $n!$ permutations as subsequences?

A subsequence can be obtained from a sequence by deleting any characters, thus it's different from a substring, whose elements have to be contiguous in the original sequence. I say this because the similar problem of finding the shortest sequence having all permutations as substrings seems to be more studied, but it's different from what I'm asking here.

Some examples of shortest supersequences:

  • $n=2\quad-\quad121$ (length 3)
  • $n=3\quad-\quad1213121$ (length 7)
  • $n=4\quad-\quad1234123142134$ (length 13 - not proven to be shortest).

It's easy to see that $n^2$ is an upper bound, since a sequence $$12\ldots n\, 12\ldots n\, \ldots\, 12\ldots n $$ ($n$ times) contains all permutations. A simple lower bound is $n(n+1)/2$, basically because $$12\ldots n\; 12\ldots (n-1)\; 12\ldots (n-2)\;\ldots $$ is too short (this can be proven rigorously). Is anything more known about this problem?

The question was asked on stack exchange, but the answer there is far from satisfactory since it gives only a broken link and no reference.

$\endgroup$
9
  • 2
    $\begingroup$ Well, if it is a string of $k$ characters, you need $k! \geq (k-n)!(n!)^{2}.$ $\endgroup$ May 6, 2014 at 11:38
  • 4
    $\begingroup$ Unfortunately, @GeoffRobinson's bound roughly gives $k \geq n^2/e^2$, so weaker than the $n(n+1)/2$ bound you already have. $\endgroup$ May 6, 2014 at 12:47
  • 5
    $\begingroup$ Here is length 12 sequence for $n=4$: 123412314231 $\endgroup$ May 6, 2014 at 14:12
  • 8
    $\begingroup$ See oeis.org/A062714 (and links)... $\endgroup$ May 6, 2014 at 14:22
  • 1
    $\begingroup$ These are not superpermutations, because here we also allow deleting characters to obtain the subsequences. $\endgroup$ Jun 6, 2023 at 7:41

2 Answers 2

22
$\begingroup$

This seems to be an open problem. It is listed in the OEIS as sequence A062714, as noted by Ilya. Summarising the most important results:

Let $m$ be the length of such a sequence. Then Newey (amongst others) describes a simple algorithm to generate them with $$m = n^2 -2n +4.$$ This is not, however, the best one. Radomirovic proves that the shortest sequences obey the tighter upper bound of $$m \le \left\lceil n^2 - \frac73 n + \frac{19}3\right\rceil.$$ A lower bound better than the trivial one shown by OP is given by Kleitman and Kwiatkowski: $$m \ge n^2 - C_\epsilon n^{7/4+\epsilon},$$ for any $\epsilon > 0$.

$\endgroup$
1
  • $\begingroup$ Can you include the link to the Encyclopedia of Integer Sequences in your answer? $\endgroup$ May 6, 2014 at 16:35
0
$\begingroup$

This is a suggestion for further development, as opposed to an answer. It seems to hold much promise.

Note that the n^2 upper bound can easily be shortened by 2, since any permutation not beginning with 1 and not ending in n does not need those letters in the example, and otherwise encodes a shorter permutation which does not need the first n or last n letters of the example.

More generally, the only permutation that "needs" all n^2 letters is the permutation with all descending letters: if a_i less than a_{i+1} then put those in the ith run, and now you can make do with one less run of letters. I believe you can extend this to chop off n-1 letters from either end when n is sufficiently large.

Even more generally, replace one of the middle runs 1...n with a shorter decreasing run n-1...2: if now there is a decrease of three or more consecutive elements, the longest or perhaps the "most central" such falling run can be placed in the middle, and the rest of the permutation on either side.

I believe a careful analysis of up down sequences in permutations will show a nice upper bound of n(n - sqrt(n)) using an example of sqrt(n) falling runs interspersed with n- 2sqrt(n) rising runs.

$\endgroup$
1
  • $\begingroup$ Upon further consideration, it seems such a model will not handle the extreme case of an oscillating permutation. A simple version with ceil(n/2) runs alternating with the same number of down runs will handle all permutations, but save only n-1 characters. $\endgroup$ May 6, 2014 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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