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.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
4 Comments »

4 Responses to “Array Rotation, Again”

  1. chaw said
    March 7, 2018 at 12:57 AM

    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)

  2. chaw said
    March 7, 2018 at 1:04 AM

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

  3. Array Rotation, Timing Tests | Programming Praxis said
    March 9, 2018 at 10:01 AM

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

  4. Daniel said
    April 1, 2018 at 6:08 AM

    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:

    [a, b, c, d, e, f, g, h]
[d, e, f, g, h, a, b, c]

Leave a comment