= Solution
Write the segment as $AB$, where $|A|=n-k$ and $|B|=k$. The desired <array rotation> is $BA$. Reverse each block, then the whole segment:
``
PROCEDURE rotate(i, n, k: INTEGER);
BEGIN
IF (k = 0) OR (k = n) THEN RETURN END;
reverse(i, n-k);
reverse(i+n-k, k);
reverse(i, n)
END rotate;
``
The state changes are $AB\to A^RB\to A^RB^R\to BA$, using the <list reversal> identity supplied in the paper and reversal being an <involution>. \b[Three reversals implement the right rotation in $O(n)$ time and $O(1)$ auxiliary space.] The initial return covers empty and identity rotations.
Back to article page
