TAOCP 7.2.1.1 Exercise 5
Let $n$ be fixed and let each array location be indexed by an $n$-bit integer.
Section 7.2.1.1: Generating All n-Tuples
Exercise 5. ▶ [22] x 5. [22] Algorithms such as the “fast Fourier transform” (exercise 4.6.4–14) often end with an array of answers in bit-reflected order, having A[(b0 . . . bn−1)2] in the place where A[(bn−1 . . . b0)2] is desired. What is a good way to rearrange the answers into proper order? [Hint: Reflect Algorithm M.]
Verified: yes
Solve time: 1m41s
Solution
Let $n$ be fixed and let each array location be indexed by an $n$-bit integer. Write any index $k$ in binary form
$$ k = (b_{n-1} b_{n-2} \dots b_0)_2, $$
and define the bit-reversal mapping $r$ by
$$ r(k) = (b_0 b_1 \dots b_{n-1})_2. $$
The array is given in the state where entry $A[k]$ is stored in position $r(k)$, so the desired rearrangement is the inverse of $r$, which is $r$ itself since $r(r(k)) = k$.
Thus the task is to restore correct order by applying an involution on indices. The permutation of indices decomposes into disjoint cycles, each cycle having length $1$ when $k = r(k)$ and length $2$ otherwise. A correct rearrangement is obtained by swapping values along each 2-cycle exactly once and leaving fixed points unchanged.
To generate each cycle exactly once, Algorithm M is applied to binary $n$-tuples, but with reversed digit interpretation. Let $(a_1,\dots,a_n)$ be the tuple generated by Algorithm M with $m_j = 2$. Interpret this tuple as the bit string $(a_1 a_2 \dots a_n)_2$ and define
$$ k = (a_1 a_2 \dots a_n)2, \qquad r(k) = (a_n a{n-1} \dots a_1)_2. $$
Since Algorithm M visits every binary $n$-tuple exactly once, every index $k$ is generated exactly once, and consequently every pair ${k, r(k)}$ is encountered twice, once when $k$ is generated and once when $r(k)$ is generated.
The in-place rearrangement is performed by executing, for each generated tuple, a conditional swap that acts only when the smaller representative of each 2-cycle is encountered. The procedure is:
For each binary $n$-tuple $(a_1,\dots,a_n)$ generated by Algorithm M, compute $k$ and $r(k)$. If $k < r(k)$, interchange $A[k]$ and $A[r(k)]$.
Correctness follows from the structure of the involution. If $k = r(k)$, no swap occurs. If $k \neq r(k)$, the pair ${k,r(k)}$ is encountered twice during the traversal, but the condition $k < r(k)$ ensures exactly one swap is performed on that pair, producing the correct final placement. Since every index belongs to exactly one cycle of the involution, all entries are placed in their correct positions.
This completes the proof. ∎