Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 4 / e

Use the convention $a_{\mathrm{new}}[j]=A[p[j]]$, as required by the paper's rotation example. Follow each permutation cycle once. Temporarily encode a visited value $v\in [0,N)$ as $-v-1$, and restore the whole permutation before returning:Require LEN(p) >= N and that p[0..N) is the stipulated permutation. Its cells must be writable and distinct from the data array. The marking map is reversible and fits whenever the original valid indices and $N$ fit in the signed integer type.

At each outer test, all marked indices belong to fully completed cycles; all unmarked cycles still contain their original data and permutation entries. Within a cycle the same shifting loop invariant as part (d) applies, with successor given by the original p: all previously filled positions have their final values, and saved preserves the overwritten first source. A permutation has no path into a different cycle, so every new successor is unmarked until it returns to s; no encoded negative value is used as a source index. At outer-loop exit every index is marked and correct. The restoration loop has decoded precisely the indices below s.

The procedure uses one extra value of type T, $O(N)$ time, and at most $N$ data reads plus $N$ data writes, with no data access for fixed points. It returns p unchanged, though it marks it temporarily. If p must remain read-only even during execution, test whether each index is its cycle's smallest member by traversing p before moving that cycle. That preserves constant space and the same optimal data accesses, but can require $O(N^2)$ index-array accesses.