CLR cover

Problem 147: Superstrings of shapes of permutations

\( \def\SMot{\mathit{Subs}} \)

Two words $u$ and $v$ of the same length are said to be order-equivalent, written $u \approx v$, if $u[i] \lt u[j]\Longleftrightarrow v[i] \lt v[j]$ for all pairs of positions $i,j$ on the words. For a word $u$ of length $n$ with all letters distinct we define $\shape(u)$ as the $n$-permutation of $\{1,2,\ldots,n\}$ order-equivalent to $u$. Define $$\SHAPES_n(w)=\{\shape(u)\,\mid\, u\ \mbox{is a factor of}\ w\ \mbox{of length}\ n\}.$$

For $n\gt 2$ there is no word containing exactly once each $n$-permutation, but in order-preserving case it is different. A word of size $n!+n-1$ containing shapes of all $n$-permutations is called a universal word, it is a superstring of shapes of all $n$-permutations. Obviously $n!+n-1$ is the smallest length of such word.

Construct, for a given $n$, a universal word of size $n!+n-1$ (shortest possible).

Use a construction similar to that for linear de Bruijn words.

References