= Array rotation
A right <array rotation> by $k$ sends the entry originally at offset $j$ to offset $(j+k)\bmod n$ for nonempty length $n$. Equivalently it changes adjacent blocks $AB$ into $BA$ when $|B|=k$. Identity rotations include $k=0$ and $k=n$.
Three reversals implement the operation: $AB\to A^RB\to A^RB^R\to BA$. Alternatively repeatedly use a <block swap> to put the smaller block in its final position and recurse on the remaining unresolved segment. Replacing that tail recursion by parameter updates gives constant auxiliary storage. If $S(a,b)$ counts swaps for blocks of lengths $a,b>0$, then $S(a,a)=a$ and $S(a,b)=\min(a,b)+S(\min(a,b),|a-b|)$ for unequal lengths. The <Euclidean algorithm> shows by <induction> that $S(a,b)=a+b-\gcd(a,b)$, so a right rotation uses $n-\gcd(n,k)$ element swaps for $0<k<n$.
Back to article page
