TAOCP 1.3.3 Exercise 34

Section 1.3.3: Applications to Permutations

Exercise 34. [M25] (Transposing blocks of data.) One of the most common permutations needed in practice is the change from $\alpha\beta$ to $\beta\alpha$, where $\alpha$ and $\beta$ are substrings of an array.

In other words, if $x_0x_1\ldots x_{m-1} = \alpha$ and $x_mx_{m+1}\ldots x_{m+n-1} = \beta$, we want to change the array $x_0x_1\ldots x_{m+n-1} = \alpha\beta$ to the array $x_mx_{m+1}\ldots x_{m+n-1}x_0x_1\ldots x_{m-1} = \beta\alpha$; each element $x_k$ should be replaced by $x_{p(k)}$ for $0 \le k < m + n$, where $p(k) = (k + m) \bmod (m + n)$. Show that every such "cyclic-shift" permutation has a simple cycle structure, and exploit that structure to devise a simple algorithm for the desired rearrangement.

Verified: yes
Solve time: 47s

Solution

Let the array be

$$ x_0x_1\ldots x_{m-1} = \alpha,\qquad x_mx_{m+1}\ldots x_{m+n-1} = \beta, $$

so that the original array is $\alpha\beta$ of length $m+n$. Define the permutation $p$ by

$$ p(k) = (k+m) \bmod (m+n),\qquad 0 \le k < m+n. $$

We analyze the cycle structure of $p$ in order to devise an efficient algorithm for transposing $\alpha$ and $\beta$ in place.

Step 1: Determine the cycle decomposition

Consider the iterates of $p$ starting from position $k = 0$. The successive images are

$$ 0 \mapsto m \mapsto 2m \mapsto 3m \mapsto \cdots \mapsto jm \mod (m+n), $$

where each image is taken modulo $m+n$. Let $g = \gcd(m,n)$. Since $p$ is a cyclic shift by $m$ modulo $m+n$, the order of $p$ is

$$ \frac{m+n}{\gcd(m,n)}. $$

Therefore the full permutation decomposes into $\gcd(m,n)$ disjoint cycles, each of length

$$ \ell = \frac{m+n}{\gcd(m,n)}. $$

Explicitly, the cycles are

$$ {k,, k+m \bmod (m+n),, k+2m \bmod (m+n),, \dots,, k+(\ell-1)m \bmod (m+n)},\quad k = 0,1,\dots,g-1. $$

No two cycles intersect, because if

$$ i + jm \equiv k + jm' \pmod{m+n}, $$

then $i-k \equiv m(j'-j) \pmod{m+n}$. Since $\gcd(m,n) = g$, this implies $i \equiv k \pmod g$. Each $k$ with $0 \le k < g$ generates exactly one distinct cycle, giving exactly $g$ disjoint cycles.

This completes the derivation of the cycle structure. Each element belongs to precisely one cycle; each cycle has length $\ell = (m+n)/g$; there are $g$ cycles.

Step 2: Algorithm exploiting the cycle structure

The cycles allow an in-place transposition of $\alpha$ and $\beta$ by successively moving elements along each cycle. Introduce a temporary variable $t$ to hold the first element of a cycle. Let the array be $x_0,\dots,x_{m+n-1}$, and let $g = \gcd(m,n)$.

For $k = 0$ to $g-1$, perform the following steps:

Set $t \leftarrow x_k$.
Initialize $j \leftarrow k$.
Repeat:
Compute $i \leftarrow (j + m) \bmod (m+n)$.
If $i = k$, break the loop.
Set $x_j \leftarrow x_i$.
Set $j \leftarrow i$.
Set $x_j \leftarrow t$.

Each iteration moves the elements along one full cycle of length $(m+n)/g$, replacing them in order without overwriting any element prematurely. After all $g$ cycles are processed, the array contains $\beta\alpha$.

Step 3: Correctness

Let $k \in {0,1,\dots,g-1}$. The cycle starting at $k$ is

$$ k,, k+m \bmod (m+n),, k+2m \bmod (m+n),, \dots,, k+(\ell-1)m \bmod (m+n), $$

with $\ell = (m+n)/g$. The assignment $x_j \leftarrow x_i$ moves each element to its target position $p(j)$. The temporary variable $t$ preserves the first element of the cycle, which closes the cycle. Since cycles are disjoint, no element is moved twice, and all elements are replaced exactly once. Hence the algorithm implements the permutation $p$ exactly.

Step 4: Complexity

Each element is moved exactly once, resulting in $m+n$ assignments of the form $x_j \leftarrow x_i$, plus $g$ temporary-variable assignments $t \leftarrow x_k$. Therefore the total number of replacements is

$$ (m+n) + g. $$

This is optimal in the sense that each element must be moved at least once, and the use of cycles avoids repeated overwriting.

Step 5: Example

Let $m = 4$, $n = 6$, so $g = \gcd(4,6) = 2$. The cycles are:

$k=0$: $0 \mapsto 4 \mapsto 8 \mapsto 2 \mapsto 6 \mapsto 0$ (length $\ell = 5$)
$k=1$: $1 \mapsto 5 \mapsto 9 \mapsto 3 \mapsto 7 \mapsto 1$ (length $\ell = 5$)

Processing each cycle as above moves all elements to produce $\beta\alpha$.

Step 6: Summary

The permutation $p(k) = (k+m) \bmod (m+n)$ decomposes into $\gcd(m,n)$ disjoint cycles of length $(m+n)/\gcd(m,n)$. Traversing each cycle with a temporary variable implements the in-place transposition $\alpha\beta \mapsto \beta\alpha$ efficiently, with exactly $m+n+g$ replacements.

This completes the proof.

∎