CLR cover

Additional Problem 12: Short Superpatterns of Permutations (Preliminary version)

We can treat a permutation $\pi$ as a permutation pattern, it matches every word order-equivalent to $\pi$ (see Problem 31). The aim here is to build a short word, called superpattern, such that each $n$-permutation is order-equivalent to its subsequence. We are interested in superpatterns having $n+1$ letters $\{1,2,\ldots,n+1\}$. Define $\alpha_n$ as increasing sequence of all odd letters, and $\beta_n$ as decreasing sequence of even letters. Define also $$ Z_n= \cases{ (\alpha_n\,\beta_n)^{n/2} & if $n$ even\cr (\alpha_n\,\beta_n)^{\lfloor n/2 \rfloor}\,\alpha_n & otherwise. } $$

We have $|Z_n|=(n^2+n)/2$. Observe that the supersequence constructed in Problem 15 is almost twice larger.

Compute in linear time an order-preserving embedding of a given permutation $\pi$ of size $n$ into $Z_n$.

References