CLR cover

Problem 137: Short supersequence of shapes of permutations

An $n$-permutation is a length-$n$ sequence (or word) of $n$ distinct elements from $\{\sa{1},\sa{2},\dots, n\}$. The aim of the problem is to build a short word ${\mathbf S}_n$, called a superpattern (supersequence of shapes), such that each $n$-permutation is order-equivalent to a subsequence of ${\mathbf S}_n$. The question is similar to finding a short supersequence but the order-preserving feature reduces drastically the length of the searched word. Indeed, the superpattern defined below has length $|{\mathbf S}_n|=(n^2+n)/2$, which is almost half the length $n^2-2n+4$ of the supersequence constructed in Problem 15.

The word ${\mathbf S}_n$ is drawn from the alphabet $\{\sa{1},\sa{2},\dots,n+1\}$ as follows. Let $\alpha_n$ be the increasing sequence of all odd letters and $\beta_n$ be the decreasing sequence of all even letters of the alphabet ($\alpha_n$ is an "ascending group" and $\beta_n$ is a "descending group"). Alternation between ascending and descending groups is the main trick of the solution. Then, define, ${\mathbf S}_n= \begin{cases} (\alpha_n\,\beta_n)^{n/2} & \mbox{if } n \mbox{ is even},\cr (\alpha_n\,\beta_n)^{\lfloor n/2 \rfloor}\,\alpha_n & \mbox{otherwise}. \end{cases}$

For a permutation $\pi=(\pi_1,\pi_2,\dots,\pi_{n})$ of $\{\sa{1},\sa{2},\dots, n\}$, let $\pi^+$ denote $(\pi_1+1,\pi_2+1,\dots,\pi_{n}+1)$, permutation of $\{\sa{2},\sa{3},\dots, n+1\}$.

An embedding of $\pi$ in a word ${\mathbf S}$ is an increasing sequence of positions $(p_1,p_2,\dots,p_n)$ on ${\mathbf S}$ that satisfies $\pi = {\mathbf S}[p_1]\,{\mathbf S}[p_2] \cdots {\mathbf S}[p_n]$.

Show how to compute in linear time an order-preserving embedding of a given $n$-permutation $\pi$ into ${\mathbf S}_n$.

Show that $\pi$ or $\pi^+$ is a (standard) subsequence of ${\mathbf S}_n$ and can be found by a greedy algorithm. Note that $\pi^+$ is order equivalent to $\pi$.

References