Rotate An Array

October 12, 2010

The easy solution is to write functions to rotate the array a single element in each direction, then call the functions for the requested count. But that means lots of intermediate assignments, so it’s slow. Instead, three well-chosen reversals can perform any rotation with a minimum of movement.

We first define a function swap! that exchanges two elements of a vector:

(define (swap! v i j)
  (let ((t (vector-ref v i)))
    (vector-set! v i
      (vector-ref v j))
    (vector-set! v j t)))

Swap! is called by reverse!, which exchanges the two elements at its endpoints, then calls itself recursively on the intermediate sub-vector, stopping when the two indices cross:

(define (reverse! v lo hi)
  (when (< lo hi)
    (swap! v lo hi)
    (reverse! v (+ lo 1) (- hi 1))))

Then rotate! reduces n modulo the length of the vector (you should confirm that this works properly whether n is positive, negative or zero) and makes three reversals. First the left half of the vector, from 0 to n-1, is reversed. Then the right half of the vector, from n to len-1, is reversed. Finally the entire vector is reversed. This leaves the vector rotated as requested:

(define (rotate! n v)
  (let* ((len (vector-length v))
         (n (modulo n len)))
    (reverse! v 0 (- n 1))
    (reverse! v n (- len 1))
    (reverse! v 0 (- len 1))))

If this seems like magic, watch what happens on our sample vector when we rotate two positions to the left. The original vector is [1 2 3 4 5 6]. Reversing the two left positions gives us [2 1 3 4 5 6]. Reversing the remaining four positions gives us [2 1 6 5 4 3]. One final reversal yields the desired result [3 4 5 6 1 2].

Jon Bentley described this algorithm for rotating an array in his Programming Pearls books, and includes pretty hand-waving pictures. Brian Kernighan and P J Plauger described it earlier, in their Software Tools books. The algorithm dates to the folklore of computing.

You can run the program at http://programmingpraxis.codepad.org/QKrX5JfK.

About these ads

Pages: 1 2

21 Responses to “Rotate An Array”

  1. […] today’s Programming Praxis exercise, our goal is to write a function to rotate an array a selected number […]

  2. Remco Niemeijer said

    My Haskell solution (see http://bonsaicode.wordpress.com/2010/10/12/programming-praxis-rotate-an-array/ for a version with comments):

    rotate :: Int -> [a] -> [a]
    rotate _ [] = []
    rotate n xs = b ++ a where (a,b) = splitAt (mod n $ length xs) xs
    

    On a side note, the given Scheme solution fails on arrays of length 0.

  3. Graham said

    Python solution, similar logic to Remco’s Haskell:

    def rotate(array, nelts):
        n = nelts % len(array)
        return array[n:] + array[:n]
    
  4. Jake said

    Here’s my solution in F#. Had to do a bit of extra work because of the way the modulus operator is defined.

  5. http://pastebin.com/5wKvVgWG

    Rotate in place with exactly n swaps and attempts to have fairly good locality.

  6. Abie said

    À la Racket. This is the first time I’ve used multiple return values.

    #lang racket
    (require (only-in rnrs/base-6 mod))

    (define (rotate a-vector rot)
    (if (<= (vector-length a-vector) 1)
    a-vector
    (call-with-values
    (λ ()
    (vector-split-at a-vector (mod rot (vector-length a-vector))))
    (λ (1st 2nd)
    (vector-append 2nd 1st)))))

  7. Axio said

    ;; Common lisp
    ;; Does return the original array, not a chunk of a circular list like
    ;; “rot l n = take (length l) $ drop (if (n>0) then n else (abs ((length l) – n))) $ cycle l”
    (defun rotate (arr n)
      (let* ((arlen (length arr))
             (new-arr (make-array arlen)))
        (loop for i below arlen
           do
             (setf (aref new-arr i) (aref arr (mod (+ i n) arlen))))
        (loop for i below arlen
           do
             (setf (aref arr i) (aref new-arr i)))))

  8. Jim Rees said

    ;; Simple, bulletproof.

    (define (reverse-range! v start end)
    (do ((i start (+ i 1))
    (j (- end 1) (- j 1)))
    ((>= i j) v)
    (let ((tmp (vector-ref v i)))
    (vector-set! v i (vector-ref v j))
    (vector-set! v j tmp))))

    (define (vector-rotate! v n)
    (let ((N (vector-length v)))
    (unless (zero? N)
    (let ((n (modulo n N)))
    (reverse-range! v 0 n)
    (reverse-range! v n N)
    (reverse-range! v 0 N)))
    v))

  9. Leandro Pacheco said

    Using python list comprehensions:

    def rotate_array(arr, rotation):
    return [arr[(rotation + i) % len(arr)] for i in range(len(arr))]

  10. Lars Björnfot said

    Here is a Java version. No recursion, just one plain loop.
    Not the shortest solution but it handles all edge cases
    (including larger left rotate than array size).

    public int[] rotate(int[] array, int count) {
    	int length = array.length;
    	if (length == 0 || count % length == 0)
    		return array;
    	count = ((count % length) + length) % length; // limit and make positive
    	int[] dest = new int[length];
    	for (int i=0; i<length; i++) {
    		int index = (i + count) % length;
    		dest[index] = array[i];
    	}
    	return dest;
    }
    
  11. nozx said

    ;; common lisp
    (defun rotate (lst arg)
    (cond
    ((null lst) lst)
    ((= (mod arg (length lst)) 0) lst)
    (t (rotate (nconc (cdr lst) (list (car lst))) (- arg 1)))))

  12. Xenmen said

    The key here is to NOT use a premade rotate function. Here’s my solution in Python:

    def rotator(arrayOld, rotateValue):
    arrayLength = arrayOld.__len__()
    while rotateValue > arrayLength: rotateValue -= arrayLength
    while rotateValue 0:
    for i in range(arrayLength):
    if i < rotateValue: arrayNew_buffer.append(arrayOld[i])
    else: arrayNew.append(arrayOld[i])
    else:
    for i in range(arrayLength):
    if i < (arrayLength + rotateValue): arrayNew_buffer.append(arrayOld[i])
    else: arrayNew.append(arrayOld[i])
    for i in arrayNew_buffer: arrayNew.append(i)
    return arrayNew

  13. swapnil Ghopade said

    /*This is My C Implementation */

    #include
    #include

    int *rotate(int *a,int size,int count)
    {

    int *c,j,temp,k=0,sign;

    c=(int *)calloc(size,sizeof(int));

    sign =count>>31;

    temp=(sign==-0x01)? (size-(-count)) : count;

    for(j=(temp);j<size;j++)
    {
    c[k]=a[j];
    k++;
    }

    for(j=0;j<(temp);j++)
    {
    c[k]=a[j];
    k++;}

    a=c;

    return a;
    }

    int main()
    {
    int *b,cnt,size,i;

    printf("Enter size of Array?");
    scanf("%d",&size);

    b=(int *)calloc(size,sizeof(int));
    for(i=0;i<size;i++)
    scanf("%d",&b[i]);

    while(1)
    {
    printf("No of elements to rotate?\n\t\tPositive Value to Rotate Left \n\t\tNegative to Right \n\t\tEnter '0' to Quit\n");
    scanf("%d",&cnt);
    if(cnt==0)
    {
    exit(0);
    }
    else{
    cnt=cnt%size;
    b=rotate(b,size,cnt);
    printf("rotated array \n");
    for(i=0;i<size;i++)
    printf("\t%d",b[i]);
    }

    }
    return 0;
    }

  14. swapnil Ghopade said

    #include
    #include

    int *rotate(int *a,int size,int count)
    {

    int *c,j,temp,k=0,sign;

    c=(int *)calloc(size,sizeof(int));

    sign =count>>31;

    temp=(sign==-0x01)? (size-(-count)) : count;

    for(j=(temp);j<size;j++)
    {
    c[k]=a[j];
    k++;
    }

    for(j=0;j<(temp);j++)
    {
    c[k]=a[j];
    k++;}

    a=c;

    return a;
    }

    int main()
    {
    int *b,cnt,size,i;

    printf("Enter size of Array?");
    scanf("%d",&size);

    b=(int *)calloc(size,sizeof(int));
    for(i=0;i<size;i++)
    scanf("%d",&b[i]);

    while(1)
    {
    printf("No of elements to rotate?\n\t\tPositive Value to Rotate Left \n\t\tNegative to Right \n\t\tEnter '0' to Quit\n");
    scanf("%d",&cnt);
    if(cnt==0)
    {
    exit(0);
    }
    else{
    cnt=cnt%size;
    b=rotate(b,size,cnt);
    printf("rotated array \n");
    for(i=0;i<size;i++)
    printf("\t%d",b[i]);
    }

    }
    return 0;
    }

  15. lalit mohan said

    My Solution in python:

    http://codepad.org/nKk5LOLl

  16. Chil Tlalli said

    You guys rock – I’m learning so much by seeing your solutions!

    Here’s my emacs lisp implementation (using a list to hold the array):

    (defun rot8r(a n)
    (if
    (= 0 (length a))
    a
    (progn
    (append
    (nthcdr (mod n (length a)) a)
    (butlast a (- (length a) (abs (mod n (length a)))))
    ))))

  17. […] Programming Praxis, Rotate An Array. I think of it more like an offset. Shift an array’s contents by ±x spaces. public static […]

  18. ckknight said

    Here’s mine in C#.

    static void RotateArrayInplace<T>(T[] array, int count)
    {
        count %= array.Length;
        if (count == 0)
            return;
        else if (count < 0)
            count += array.Length;
    
        T[] tmp = new T[count];
        Array.Copy(array, tmp, count);
        Array.Copy(array, count, array, 0, array.Length - count);
        Array.Copy(tmp, 0, array, array.Length - count, count);
    }
    
    static T[] RotateArray<T>(T[] array, int count)
    {
        count %= array.Length;
        if (count == 0)
            return (T[])array.Clone();
        else if (count < 0)
            count += array.Length;
    
        T[] result = new T[array.Length];
        Array.Copy(array, 0, result, array.Length - count, count);
        Array.Copy(array, count, result, 0, array.Length - count);
        return result;
    }
    
  19. Jebb said

    Did it in C, rotating the array in place instead of returning a new one. The actual rotation in my solution involves (n + gcd(n, offset)) assignments, using no additional memory appart from a single temp variable. If n and offset are coprime, we can rotate the array in a single pass; if not, we need to break it down in gcd(n, offset) sub-problems.

    void rotate(int *array, int len, int offset)
    {
    	int i, j, gcd, tmp;
    	while (offset < 0)
    		offset += len;
    	gcd = _gcd(offset,len);
    	for (j = 0; j < gcd; j++) {
    		tmp = array[offset % len + j];
    		for (i = len / gcd; i > 1; i--)
    			array[(i + 1) * offset % len + j] = array[i * offset % len + j];
    		array[2 * offset % len + j] = tmp;
    	}
    }

    (the _gcd function is the one we’ve written for the 15 January 2010 exercise)

    I find the code hard to understand, don’t know how to make it any easier to read. To help clarify a bit, here’s what’s happening when rotating an array of length 9 by an offset of 5:
    5 -> tmp
    0 -> 5
    4 -> 0
    8 -> 4
    3 -> 8
    7 -> 3
    2 -> 7
    6 -> 2
    1 -> 6
    tmp -> 1

    and the same array by an offset of 6:
    6 -> tmp
    0 -> 6
    3 -> 0
    tmp -> 3
    7 -> tmp
    1 -> 7
    4 -> 1
    tmp -> 4
    8 -> tmp
    2 -> 8
    5 -> 2
    tmp -> 5

  20. hash1baby said

    This can be done with constant space cost, since translation by offset = reflection at origin followed by reflection at (origin + offset). Reflection can be implemented by swapping elements pairwise in place.

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 )

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

Follow

Get every new post delivered to your Inbox.

Join 634 other followers

%d bloggers like this: