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
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
        i -= j
        j -= 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
            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)

You can run the program at


Pages: 1 2

3 Responses to “Array Rotation, Again”

  1. chaw said

    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)
            (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))
            (let ((e (- n d)))
              (if (<= d e)
                    (vector-swap-disjoint-ranges! vec d start (- end d))
                    (vector-range-rotate-left! vec d start (+ start e)))
                    (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))
            (f (+ d 1))))))

  2. chaw said

    Minor point: The tests included in the solution by @programmingpraxis
    mutate literal vectors, which I believe is forbidden by standard

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: