TAOCP 1.3.3 Exercise 35

Let the initial array be indexed $0,1,\ldots,l+m+n-1$ and written x_0x_1\cdots x_{l+m+n-1}=\alpha\beta\gamma, where

taocpmathematicsalgorithmsvolume-1math-hard

Section 1.3.3: Applications to Permutations

Exercise 35. [M30] Continuing the previous exercise, let $x_0x_1\ldots x_{l+m+n-1} = \alpha\beta\gamma$ where $\alpha$, $\beta$, and $\gamma$ are strings of respective lengths $l$, $m$, and $n$, and suppose that we want to change $\alpha\beta\gamma$ to $\gamma\beta\alpha$. Show that the corresponding permutation has a convenient cycle structure that leads to an efficient algorithm. [Exercise 34 considered the special case $m = 0$.] Hint: Consider changing $(\alpha\beta)(\gamma\beta)$ to $(\gamma\beta)(\alpha\beta)$.

Verified: yes
Solve time: 57s

Setup

Let the initial array be indexed $0,1,\ldots,l+m+n-1$ and written

$$ x_0x_1\cdots x_{l+m+n-1}=\alpha\beta\gamma, $$

where

$$ \alpha=x_0\cdots x_{l-1},\quad \beta=x_l\cdots x_{l+m-1},\quad \gamma=x_{l+m}\cdots x_{l+m+n-1}. $$

Let $p$ be the permutation on ${0,1,\ldots,l+m+n-1}$ determined by the transformation $\alpha\beta\gamma \mapsto \gamma\beta\alpha$. The condition means

$$ x_k \mapsto x_{p(k)}. $$

Thus $p$ is determined by block relocation:

$$ \alpha\to \text{final positions of }\gamma\alpha,\quad \beta\to \text{middle block},\quad \gamma\to \text{front block}. $$

We must determine the cycle structure of $p$.

Solution

Define $N=l+m+n$. The final arrangement $\gamma\beta\alpha$ occupies intervals

$$ \gamma: 0,\ldots,n-1,\quad \beta: n,\ldots,n+m-1,\quad \alpha: n+m,\ldots,N-1. $$

Hence $p$ is given by

$$ p(k)= \begin{cases} n+m+k, & 0\le k<l,\ n+(k-l), & l\le k<l+m,\ k-(l+m), & l+m\le k<N. \end{cases} $$

Let $d=\gcd(l,m,n)$. Consider $k\in{0,\ldots,N-1}$ and write $k\equiv r \pmod d$. Since each of $l,m,n$ is divisible by $d$, each of the increments $n+m$, $n-l$, and $-(l+m)$ is congruent to $0 \pmod d$. Hence

$$ p(k)\equiv k \pmod d, $$

so each residue class modulo $d$ is invariant under $p$.

Fix a residue class $r$ modulo $d$, and choose $k$ in that class. The orbit of $k$ under $p$ is contained in the same class. It remains to show that the orbit has size exactly $N/d$.

Let $S$ be the set of all integer linear combinations of $l,m,n$:

$$ S={al+bm+cn : a,b,c\in\mathbb Z}. $$

Since $d=\gcd(l,m,n)$, the set $S$ equals $d\mathbb Z$.

Each application of $p$ moves an index by one of the increments

$$ n+m,\quad n-l,\quad -(l+m), $$

depending on the block containing the current index. Each of these increments lies in $S$. Therefore any difference between two indices in the same orbit lies in $S$.

Conversely, starting from any $k$, repeated application of $p$ allows traversal between blocks in a way that produces net displacements generated by $l,m,n$, hence by $S$. Thus every index congruent to $k$ modulo $d$ is reachable from $k$.

Therefore the orbit of $k$ is exactly the residue class of $k$ modulo $d$, and each orbit has size $N/d$.

Since the orbits of a permutation are its cycles, the permutation $p$ is the product of exactly $d$ disjoint cycles, each of length $N/d$.

Verification

Each formula for $p(k)$ places $\alpha,\beta,\gamma$ into disjoint target intervals whose concatenation is $0,\ldots,N-1$, so $p$ is a well-defined bijection on ${0,\ldots,N-1}$.

The congruences $n+m\equiv 0$, $n-l\equiv 0$, and $-(l+m)\equiv 0 \pmod d$ follow directly from $d\mid l$, $d\mid m$, and $d\mid n$. Hence $p(k)\equiv k\pmod d$ holds in each of the three cases.

Since every step of $p$ preserves residue class modulo $d$, no orbit can intersect two different residue classes. Since the generating increments lie in $d\mathbb Z$, every index in the same residue class is connected by repeated application of $p$, so no proper subset of a residue class is invariant under $p$.

Thus each residue class forms exactly one cycle.

This completes the proof. ∎