TAOCP 5.2 Exercise 10
We are given an array of records \(R[1\ldots N]\) and a permutation \(p(1)\ldots p(N)\) of \(\{1,\ldots,N\}\).
Exercise 10. [25] Design an efficient algorithm that replaces the $N$ quantities $(R_1, \ldots, R_N)$ by $(R_{\sigma(1)}, \ldots, R_{\sigma(N)})$, respectively, given the values of $R_1, \ldots, R_N$ and the permutation
$p(1) \ldots p(N)$ of ${1, \ldots, N}$. Try to avoid using excess memory space. (This problem arises if we wish to rearrange records in memory after an address table sort, without having enough room to store $2N$ records.)
Verified: no
Solve time: 7m23s
Solution
We are given an array of records (R[1\ldots N]) and a permutation (p(1)\ldots p(N)) of ({1,\ldots,N}). The goal is to rearrange the records in place so that the new sequence becomes [ (R_{p(1)},,R_{p(2)},,\ldots,,R_{p(N)}), ] i.e. for each (i) the record originally at position (p(i)) moves to position (i). The permutation is stored in an array (P[1\ldots N]) with (P[i]=p(i)); we are allowed to modify (P) during the algorithm. Only (O(1)) additional memory may be used.
Algorithm P (In-place permutation)
P1. [Loop on (i).] For (i = 1,2,\ldots,N), if (P[i]\neq 0) perform steps P2-P4; otherwise continue with the next (i).
P2. [Start cycle.] Set (\text{start}\leftarrow i), (j\leftarrow i), (\text{temp}\leftarrow R[j]).
P3. [Advance.] Set (k\leftarrow P[j]). If (k = \text{start}) go to step P4. Otherwise set (R[j]\leftarrow R[k]), (P[j]\leftarrow 0), (j\leftarrow k), and repeat step P3.
P4. [Finish cycle.] Set (R[j]\leftarrow \text{temp}), (P[j]\leftarrow 0). (\blacksquare)
Correctness
The permutation (P) decomposes uniquely into disjoint cycles. Consider one such cycle
[
i_1 ;\rightarrow; i_2 ;\rightarrow; \cdots ;\rightarrow; i_m ;\rightarrow; i_1,
]
where (P[i_1]=i_2,; P[i_2]=i_3,;\ldots,; P[i_m]=i_1).
When the outer loop (P1) reaches the first unprocessed element of this cycle, say (i_1), we have (P[i_1]\neq0). Steps P2-P4 execute with (\text{start}=i_1), (j=i_1), (\text{temp}=R[i_1]).
Iteration 1 (P3): (j=i_1), (k=P[i_1]=i_2\neq\text{start}). We set (R[i_1]\leftarrow R[i_2]), (P[i_1]\leftarrow0), (j\leftarrow i_2).
Iteration 2: (j=i_2), (k=P[i_2]=i_3\neq\text{start}). Set (R[i_2]\leftarrow R[i_3]), (P[i_2]\leftarrow0), (j\leftarrow i_3).
(\cdots)
Iteration (m): (j=i_m), (k=P[i_m]=i_1=\text{start}). The test (k=\text{start}) succeeds, so we go to P4.
P4: Set (R[i_m]\leftarrow\text{temp}) (the original (R[i_1])), (P[i_m]\leftarrow0).
After the cycle finishes, the records satisfy [ R[i_1]=\text{orig. }R[i_2],; R[i_2]=\text{orig. }R[i_3],;\ldots,; R[i_m]=\text{orig. }R[i_1], ] which is exactly the desired permutation. All entries (P[i_1],\ldots,P[i_m]) have been set to (0). Because cycles are disjoint, every index is processed exactly once; the outer loop skips indices already zeroed. The algorithm terminates after at most (N) outer iterations and exactly (N) executions of step P3 in total.
Invariant: Before each iteration of P1, all indices (<i) that belong to completed cycles have their records in final position and (P[j]=0); the remaining indices form a set of disjoint cycles of the original permutation with (P[j]>0).
This completes the proof. ∎
Complexity
The algorithm uses only a constant number of extra variables ((\text{start}, j, k, \text{temp})), hence (O(1)) additional space. Each record is moved once and each permutation entry is examined a constant number of times, giving (O(N)) time. This is optimal because any algorithm must at least read all (N) records and all (N) permutation entries.
Notes
If the permutation array (P) must be preserved, one can use the sign bit of each entry (assuming the machine represents integers with a sign) to mark visited elements instead of zeroing them, still using (O(1)) extra space. If no such bit is available, a separate bit vector of length (N) would be required, which uses (O(N)) bits of extra space.