TAOCP 7.1.3 Exercise 53

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 53. ▶ [M25] The permutations in exercise 52 are said to be "induced by a permutation of index digits," because we obtain $j\pi$ by permuting the binary digits of $j$. Suppose $j\pi = (j_{(d-1)\nu}\ldots j_{1\nu}j_{0\nu})_2$, where $\upsilon$ is a permutation of ${0, 1, \ldots, d-1}$. Prove that if $\upsilon$ has $t$ cycles, the $2^d$-bit permutation $x \mapsto x^*$ can be obtained with only $d - t$ swaps. In particular, show that this observation speeds up all four cases of exercise 52.

Verified: no
Solve time: 1m09s

Solution

Let $\upsilon$ be a permutation of ${0,1,\ldots,d-1}$, and let $j = (j_{d-1}\ldots j_1 j_0)_2$. The induced permutation on indices is

$$ j\pi = (j_{(d-1)\upsilon}\ldots j_{1\upsilon} j_{0\upsilon})_2, $$

so $\pi$ permutes coordinate positions of the binary vector representation of each index.

For each $j \in {0,1,\ldots,2^d-1}$, write $j = (j_{d-1},\ldots,j_0)$ as a binary $d$-tuple. Then $j\pi$ is obtained by permuting coordinates:

$$ (j_0,\ldots,j_{d-1}) \mapsto (j_{0\upsilon},\ldots,j_{(d-1)\upsilon}). $$

Thus $\pi$ is the natural action of $\upsilon$ on the coordinates of the $d$-dimensional Boolean cube.

Let $x = (x_j){0 \le j < 2^d}$, and define $x^$ by $x^__{j\pi} = x_j$. The transformation $x \mapsto x^*$ permutes coordinates of the $2^d$-tuple indexed by vertices of the cube.

Decompose $\upsilon$ into disjoint cycles on ${0,1,\ldots,d-1}$. Let one cycle be

$$ (i_1, i_2, \cdots, i_k), $$

so $\upsilon(i_\ell)=i_{\ell+1}$ for $1 \le \ell < k$ and $\upsilon(i_k)=i_1$.

Fix such a cycle. For each index $j = (j_{d-1},\ldots,j_0)$, define a local operation $T(i_a,i_b)$ that swaps the bits in positions $i_a$ and $i_b$ in every index simultaneously; that is, it maps each coordinate $x_j$ to $x_{j'}$ where $j'$ is obtained from $j$ by exchanging the $i_a$-th and $i_b$-th bits. This operation is an involution, and applying it twice restores every coordinate.

Consider the composition

$$ T(i_1,i_2), T(i_2,i_3), \cdots, T(i_{k-1},i_k). $$

Let $j$ be any index. Tracking its coordinate bits through this sequence shows that each bit in positions $i_1,\ldots,i_k$ is rotated according to the cycle $(i_1,\cdots,i_k)$, while all other bit positions remain fixed. Hence this composition realizes the restriction of $\upsilon$ to this cycle.

Each operation $T(i_a,i_{a+1})$ is a single swap, so this cycle contributes exactly $k-1$ swaps.

Summing over all cycles of $\upsilon$, if the cycle decomposition has $t$ cycles and the cycle lengths are $k_1,\ldots,k_t$, then the total number of swaps is

$$ \sum_{s=1}^t (k_s - 1) = \left(\sum_{s=1}^t k_s\right) - t = d - t, $$

since the cycles partition ${0,1,\ldots,d-1}$.

Thus the permutation $x \mapsto x^*$ can be implemented using exactly $d-t$ swaps.

This completes the proof. ∎