#
Problem 15: Short Supersequence of Permutations

\(
\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.