TAOCP 7.1.3 Exercise 62

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 62. ▶ [22] Let $N = 2^d$. We can obviously represent a permutation $\pi$ of ${0, 1, \ldots, N-1}$ by storing a table of $N$ numbers, $d$ bits each. With this representation we have instant access to $y = x\pi$, given $x$; but it takes $\Omega(N)$ steps to find $x = y\pi^-$ when $y$ is given.

Show that, with the same amount of memory, we can represent an arbitrary permutation in such a way that $x\pi$ and $y\pi^-$ are both computable in $O(d)$ steps.

Verified: yes
Solve time: 1m13s

Solution

Let $N = 2^d$. Consider the standard Beneš permutation network on $N$ inputs. It is a rearrangeable network with $2d-1$ stages, each stage consisting of $N/2$ switching elements, each switching element connecting two wires and having one control bit that either keeps the wires straight or crosses them.

A permutation $\pi$ of ${0,1,\ldots,N-1}$ is represented by assigning one control bit to each switching element in each stage so that the resulting network routes input line $x$ to output line $x\pi$.

A Beneš network with $N = 2^d$ has exactly $(2d-1)\cdot (N/2)$ switching elements. Each element stores one bit. The total number of bits is

$$ (2d-1)\frac{N}{2} = \Theta(Nd). $$

Since the standard representation stores $N$ values each of $d$ bits, its size is exactly $Nd$ bits, and the network representation uses the same order of memory.

To compute $y = x\pi$, start with the input wire index $x$ and simulate propagation through the network. At stage $k$, the current wire index is updated by applying the control bit of the unique switching element incident to that wire in that stage. This update determines whether the wire remains in its current pair or swaps within its pair, and also updates its position within the stage. Each stage performs a constant number of bit tests and conditional swaps on a $d$-bit index representing the wire label. Since there are $2d-1$ stages, the total number of steps is $O(d)$.

To compute $x = y\pi^{-}$, the inverse permutation, the same network is traversed in reverse stage order. Each switching element is symmetric: the same control bit determines the routing in both directions. Thus, starting from output wire $y$, one applies the stages in reverse order, updating the wire index by the same constant-time local rule. Again each stage contributes $O(1)$ operations, giving total time $O(d)$.

The construction is valid because the Beneš network is rearrangeable: for every permutation $\pi$ there exists an assignment of control bits that realizes $\pi$, a standard property proved by recursive decomposition of permutations on $2^{d-1}$ inputs in the first and last stages, with the middle subnetwork handling the induced subpermutation.

Therefore, using $Nd$ bits of storage, one can represent any permutation of ${0,1,\ldots,N-1}$ so that both $x\pi$ and $y\pi^{-}$ are computable in $O(d)$ steps. ∎