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.

Advertisements

Pages: 1 2

4 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)
          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

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

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

  4. Daniel said

    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 Reply

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

WordPress.com Logo

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

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s

%d bloggers like this: