20
$\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$
  • 2
    $\begingroup$ Well, if it is a string of $k$ characters, you need $k! \geq (k-n)!(n!)^{2}.$ $\endgroup$ – Geoff Robinson May 6 '14 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$ – David E Speyer May 6 '14 at 12:47
  • $\begingroup$ It would be interesting even to see how to efficiently encode this as a Boolean satisfiability problem. $\endgroup$ – Steve Huntsman May 6 '14 at 13:18
  • 5
    $\begingroup$ Here is length 12 sequence for $n=4$: 123412314231 $\endgroup$ – Ilya Bogdanov May 6 '14 at 14:12
  • 8
    $\begingroup$ See oeis.org/A062714 (and links)... $\endgroup$ – Ilya Bogdanov May 6 '14 at 14:22
20
$\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$
  • $\begingroup$ Can you include the link to the Encyclopedia of Integer Sequences in your answer? $\endgroup$ – Mateus Araújo May 6 '14 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$
  • $\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$ – The Masked Avenger May 6 '14 at 18:21

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.