CLR cover

Additional Problem 14: Universal Words of Permutations (Preliminary version)

\( \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(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 there is a word $W$ over a larger linearly ordered alphabet such that for each permutation $\pi$ there is exactly one subword of $W$ order-equivalent to $\pi$. In other words $|W|=n!+n-1$ and $SHAPES(W)$ is the set of all $n$-permutations. Such words $W$ are called $n$-universal words of permutations.

In other words the word $|W|$ of size $n!+n-1$ is universal if and only if $SHAPES(W)$ is the set of all $n$-permutations.

The crucial operation in the greedy generation presented here of a universal word is the shape-extension of an $(n-1)$-permutation $\alpha=(a_1,a_2,\ldots,a_{n-1})$ of distinct numbers. Assume $(b_1,b_2,\ldots,b_{n-1})$ is the sorted version of $\alpha$. Define $b_0=-\infty,b_n=+\infty$. Then for $k\geq 1 $ denote $$Level_k(\alpha)=\{x \mid b_{k-1}\lt x\lt b_k\} $$ and $$ ExtShape(\alpha,k)=shape(\alpha\,a) \ \mbox{for any}\ a\in Level_k(\alpha). $$

Observation

If $x,y\in Level_k(\alpha)$ then $shape(\alpha\,x) = shape(\alpha\,y)$.

Denote by $suf_{n-1}(W)$ the suffix of $W$ of length $n-1$.

GREEDY$(n \textrm{ positive integer})$ 
    \begin{algorithmic}
  \STATE{$W\leftarrow a_1\,a_2\,\ldots,a_{n-1}\ \mbox{where}\ a_1\lt a_2\lt \cdots\lt a_{n-1}$}
  \FOR{$i\leftarrow 1$ to $n!$}
     \STATE{$\alpha\leftarrow suf_{n-1}(W)$}
     \STATE{$k\leftarrow \min\{j\geq 1 \mid ExtShape(\alpha,j) \notin SHAPES(W)\}$}
     \STATE{$(*)$ let $a$ be any real number in $Level_k(\alpha)$}
     \STATE{$W\leftarrow W\,a$}
  \ENDFOR
  \RETURN{$W$}
    \end{algorithmic}

Observation

Usually the output of the algorithm is a sequence of real numbers, not necessarily integers.

Prove the correctness of the algorithm GREEDY.

References