## 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

### 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]
```