Example
\(
\def\sa#1{\tt{#1}}
\def\dd{\dot{}\dot{}}
\newcommand{\Arrow}[1]{\,\stackrel{#1}{\longrightarrow}\,}
\)
Recall that we number positions in permutations starting from 0,
but the $n$-permutations consist of numbers from $\{1,2,\ldots,n\}$.
We have $\alpha_3=12121$ and the generation of $\{1,2,3\}$ is:
$$123\Arrow{1} 213 \Arrow{2} 312\Arrow{1} 132\Arrow{2} 231 \Arrow{1} 321$$
The generation of all 24 permutations of $\{1,2,3,4\}$ has the following structure.
$$1234\Arrow{\alpha_3} 3214\Arrow{3}4123 \Arrow{\alpha_3} 2143\Arrow{3}$$
$$ 3412 \Arrow{\alpha_3} 1432 \Arrow{3} 2341 \Arrow{\alpha_3} 4321$$
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.
References
-
G. Ehrlich,
Loopless algorithms for generating permutations, combinations,
and other combinatorial configurations,
J. ACM 20(3) (1973) 500-513.
-
J. Sawada and A. Williams,
Greedy flipping of pancakes and burnt pancakes,
Discret. Appl. Math. 210 (2016) 61-74.
-
S. Zaks,
A new algorithm for generation of permutations,
BIT 24(2) (1984) 196-204.
