= Solution
Use the convention \b[$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:
``
PROCEDURE Permute(VAR p: ARRAY OF INTEGER);
VAR s, j, next: INTEGER; saved: T;
BEGIN
s := 0;
WHILE s < N DO
IF p[s] >= 0 THEN
IF p[s] = s THEN
p[s] := -p[s]-1
ELSE
saved := a[s]; j := s;
next := p[j]; p[j] := -next-1;
WHILE next # s DO
a[j] := a[next]; j := next;
next := p[j]; p[j] := -next-1
END;
a[j] := saved
END
END;
s := s+1
END;
s := 0;
WHILE s < N DO p[s] := -p[s]-1; s := s+1 END
END Permute;
``
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`.
\b[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.
Back to article page
