CLR cover

Problem 135: The words representing combinatorial generations

There are many interesting strings related to combinatorial generations, their characteristic feature is usually high compressibility. Here we discuss permutation generations. Usually they 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. The most interesting are cases when this alphabet is small. We present in detail two generation sequences $\alpha_n,\beta_n$, then in the notes we mention briefly sequences $\gamma$ and $\Phi$. Assume the permutation of numbers $\{1,2,\ldots,n\}$ is stored in the table $\pi$, with positions numbered from zero.

Reversing prefixes

In this generation the 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$.

$\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.

$\rho_n$ can be also generated on-line using extra memory of size $O(n)$. Assume we know the factorial representation of $n-1$: $$n-1=a_1\cdot 1+a_2\cdot 2!+a_3\cdot 3! +\cdots +a_m\cdot m!,$$ where $0\le a_i \le i!$ for each $i$ and $a_m\ne 0$. Then $\rho_n$ equals the first position $k$ such that $a_k\lt k$ or $k=m+1$. We obtain factorial representation of $n$ by increasing $a_k$ by 1 and set $a_i=0$ for all $i\lt k$.

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$ generates all $n$-permutations and can be described by an SLP of size $O(n\log n)$. Show also that each SLP of any generating sequence for $n$-permutations is of $\Omega(n\log n)$ size.

References