CLR cover

Additional Problem 10: SLP-Compression of Permutation Generating Sequence (Preliminary version)

Usually the permutation generating algorithms produce each successive permutation by applying some kind of a basic operation. The sequence of this operations, corresponding to the permutation ordering, is called the generating sequence. It is treated as a word over the alphabet consisting of names of basic operations.

Assume the permutation of numbers $\{1,2,\ldots,n\}$ is stored in the table $\pi$, with positions numbered from zero. Our alphabet of basic operations is $\Sigma_n=\{1,2,\ldots,n-1\}$.

The symbol $i$ corresponds to the basic operation: reverse the prefix $\pi[0\dd i]$ of permutation $\pi$.

We define the sequence $\alpha_n$ as a prefix of size $n!-1$ of the following sequence $\rho\,=\,(\rho_1,\rho_2,\rho_3,\ldots )$, where $$\rho_k= \max \lbrace j \mid j! \ \mbox{is a divisor of}\ k \rbrace, \ \mbox{for}\ k\geq 1.$$ We have $\rho\,=\, 1\,2\,1\,2\,1\,3\,1\,2\,1\,2\,1\,3\, 1\,2\, \ldots$, $\rho_{12} = 3$, $\rho_{44} = 2$, $\rho_{13} = 1$.

$\alpha_n$ is a generating sequence: starting from the id-permutation $\pi=(\pi_0,\pi_1,\pi_2,\ldots,\pi_{n-1})\,=\, (1,2,\ldots,n),$ and consecutively applying operations from $\alpha_n$ all $n$-permutations are generated, each exactly once.

We consider compression in terms of straight-line programs. A straight-line program, briefly SLP, is a context-free grammar that produces a single word $w$ over a given alphabet $\Sigma$.

An SLP can be also defined as a sequence of recurrences (equations), using operations of concatenation of words. Compression by straight-line programs is also called Grammar-Based Compression.

Show that the generating sequence $\alpha_n$ can be described by an SLP of size $O(n\log n)$.
Then show that $\alpha_n$ is a sequence generating all permutations of $\{1,2,\ldots,n\}$, starting from $[1,2,\ldots,n]$.

Show that each SLP of any generating sequence for $n$-permutation requires $\Omega(n\log n)$ size - $\alpha_n$ is asympthotically optimal.