CLR cover
Previous problem

Problem 15: Short Supersequence of Permutations

Next problem
\( \def\sa#1{\tt{#1}} \)

The problem deals with the idea of storing efficiently a set of patterns into a word. Contrary to the definition of a superword, in this problem patterns are stored as subsequences of a word called a supersequence.

The present patterns called $n$-permutations are drawn from the alphabet $\{\sa{1},\sa{2},\dots,n\}$. They are words in which every number from $\{\sa{1},\sa{2},\dots,n\}$ appears exactly once. The aim is to build words, called $n$-supersequences, that contain all $n$-permutations as subsequences.

For $n=3$ the word $\sa{1213212}$ of length $7$ is a shortest $3$-supersequence. For $n=4$ the word $\sa{123412314321}$ of length $12$ is a shortest $4$-supersequence. These two supersequences are of lengths $n^2-2n+4$ (for $n=3,4$). Observe that for $n=4$ our $4$-supersequence has length $12$ while a shortest $4$-superword, obviously longer, is of length $33$ (see Problem 14).

A simple way to produce an $n$-supersequence is to consider a word of the form $\pi^n$ for any $n$-permutation $\pi$, or of the form $\pi_1\,\pi_2\,\pi_3\, \cdots\, \pi_n$ where $\pi_i$s are any $n$-permutations. It is clear they contain all the $n!$ $n$-permutations as subsequences but their length is $n^2$, far from optimal.

The aim of the problem is to show how to construct a moderately short $n$-supersequence, which may not be of minimal length.

Show how to construct an $n$-supersequence of length $n^2-2n+4$ for each natural number $n$.
Starting from a straight $n$-supersequence of length $n^2$, show how to tune it to get the required length.

References

  • S. P. Mohanty. Shortest string containing all permutations. Discrete Mathematics, 31:91-95, 1980.
  • E. Zalinescu. Shorter strings containing all k-element permutations. Inf. Process. Lett., 111(12):605-608, 2011.