Array Rotation, Again
March 6, 2018
Here is Bentley’s solution, which he credits to David Gries and Harlan Mills; function swap(a,b,m) exchanges x[a..a+m-1) with x[b..b+m-1):
if rotdist == 0 or rotdist == n
return
i = p = rotdist
j = n - p
while i != j
/* invariant:
x[0 ..p-i ] in final position
x[p-i..p-1 ] = a (to be swapped with b)
x[p ..p+j-1] = b (to be swapped with a)
x[p+j..n-1 ] in final position
*/
if i > j
swap(p-i,p,j)
i -= j
else
swap(p-i,p+j-i,i)
j -= i
swap(p-i,p,i)
Here is our version of that code:
(define (rotate x rotdist)
(define (swap a b m)
(do ((i 0 (+ i 1))) ((= i m) x)
(let ((t (vector-ref x (+ a i))))
(vector-set! x (+ a i)
(vector-ref x (+ b i)))
(vector-set! x (+ b i) t))))
(let ((n (vector-length x)) (p rotdist))
(let loop ((i p) (j (- n p)))
(cond ((= i j) (swap (- p i) p i) x)
((> i j) (swap (- p i) p j)
(loop (- i j) j))
(else (swap (- p i) (+ p j (- i)) i)
(loop i (- j i)))))))
> (rotate '#(a b c d e f g h) 3) #(d e f g h a b c) > (rotate '#(d e f g h a b c) 5) #(a b c d e f g h)
Bentley points out that the code is isomorphic to this (slow but correct) additive Euclidean algorithm for computing the greatest common divisor of i and j, which assumes that neither input is zero:
int gcd(int i, int j)
while i != j
if i > j
i -= j
else
j -= i
return i
Or, in Scheme:
(define (gcd i j)
(let loop ((i i) (j j))
(if (= i j) i
(if (> i j)
(loop (- i j) j)
(loop i (- j i))))))
> (gcd 28 35) 7
You can run the program at https://ideone.com/wBHxJD.
Programming Praxis 
Here is an implementation in standard R7RS Scheme.
(import (scheme base) (scheme write)) (define (vector-swap! v i j) (let ((t (vector-ref v i))) (vector-set! v i (vector-ref v j)) (vector-set! v j t))) ;; [start1, ..., start1+n-1] and [start2, ..., start2+n-1] must be disjoint. ;; TODO? handle non-disjoint cases too. (define (vector-swap-disjoint-ranges! v n start1 start2) (if (<= n 0) v (begin (vector-swap! v start1 start2) (vector-swap-disjoint-ranges! v (- n 1) (+ start1 1) (+ start2 1))))) ;; left-rotate vec[start..end-1] by steps positions. ;; negative steps => rotate -steps right (define (vector-range-rotate-left! vec steps start end) (let* ((n (- end start)) (d (floor-remainder steps n))) (if (or (zero? d) (< n 2)) vec (let ((e (- n d))) (if (<= d e) (begin (vector-swap-disjoint-ranges! vec d start (- end d)) (vector-range-rotate-left! vec d start (+ start e))) (begin (vector-swap-disjoint-ranges! vec e start (- end e)) (vector-range-rotate-left! vec (- d e) (+ start e) end))))))) (define (vector-rotate-left! vec steps) (vector-range-rotate-left! vec steps 0 (vector-length vec))) (define (test) (let ((v '#(0 1 2 3 4 5 6 7 8 9))) (let f ((d -12)) (when (<= d 12) (display d) (display (vector-rotate-left! (vector-copy v) d)) (newline) (f (+ d 1)))))) (test)Minor point: The tests included in the solution by @programmingpraxis
mutate literal vectors, which I believe is forbidden by standard
Scheme.
[…] Programming Pearls in the last two exercises, and have implemented his “juggling” and “block swap” algorithms. Bentley also discusses a third algorithm, which he calls the “reversal” […]
Here’s a solution in C.
#include <stdio.h> #include <stdlib.h> void print_array(char* array, size_t n) { printf("["); for (size_t i = 0; i < n; ++i) { if (i != 0) printf(", "); printf("%c", array[i]); } printf("]\n"); } static void swap(char* a1, char* a2, size_t n) { for (size_t i = 0; i < n; ++i) { char tmp = a1[i]; a1[i] = a2[i]; a2[i] = tmp; } } void rotate(char* array, size_t n, size_t i) { i %= n; while (1) { if (n <= 1 || i == 0) break; if (i == n - i) { swap(array, array + i, i); break; } else if (i < n - i) { swap(array, array + n - i, i); n -= i; } else { swap(array, array + i, n - i); array += n - i; size_t n_ = n; n = i; i -= n_ - i; } } } int main(void) { char array[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'}; size_t n = sizeof(array) / sizeof(char); print_array(array, n); rotate(array, n, 3); print_array(array, n); return EXIT_SUCCESS; }Output: