## Array Rotation, Again

### March 6, 2018

Here is Bentley’s solution, which he credits to David Gries and Harlan Mills; function `swap(`

exchanges *a*,*b*,*m*)*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.

Advertisements

Pages: 1 2

Here is an implementation in standard R7RS Scheme.

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” […]