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

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

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

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

Python solution, similar logic to Remco’s Haskell:

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

http://pastebin.com/5wKvVgWG

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

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

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

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

Using python list comprehensions:

def rotate_array(arr, rotation):

return [arr[(rotation + i) % len(arr)] for i in range(len(arr))]

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

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

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

/*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;

}

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

}

My C ImplementationMy Solution in python:

http://codepad.org/nKk5LOLl

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

))))

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

Here’s mine in C#.

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.

(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

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.

Hello I am new

//_________________________________________________________//

#include

using namespace std;

//_________________________________________________________//

//Function to Determine Absolute and to account for Extremities

int AbsolShiftfunc (int User , int ArrSize)

{

int Absolshift;

int ShiftType;

if (User>=0)

{

Absolshift = User;

ShiftType = 1;

if (UserArrSize)

{

while(Absolshift>ArrSize)

{

Absolshift = Absolshift – ArrSize;

}

}

}

else if (User<=0)

{

Absolshift = -User;

ShiftType = 0;

if (-User ArrSize)

{

while(Absolshift>ArrSize)

{

Absolshift = Absolshift – ArrSize;

}

}

}

if (ShiftType == 1)

{

return Absolshift;

}

else if (ShiftType == 0)

{

return -Absolshift;

}

}

//_________________________________________________________//

int IndivShiftfunc (int Initial , int Absolshift, int ArrSize)

{

int Destindex = Initial+(Absolshift);

if (Destindex >= ArrSize )

{

while (Destindex >= ArrSize)

{

Destindex = Destindex – ArrSize;

}

}

if (Destindex < 0 )

{

while (Destindex ArrSize)

{

Destindex = Destindex + ArrSize;

}

}

return Destindex;

}

//_______________________________________________________//

void Solution()

{

//Declaring Arbitary Original Array And Copy

const int size = 700;

int ArrO[size];

int ArrC[size];

int Arrsize = 0;

//Pretaining to shifting

int Usershift;

int AbsoluteShift;

int Destinationindex;

//LCV

const int Sentinel = -999;

//Asking user to specify values and Computing Recquired Array Size

cout<<"\n\n\n\n\n";

cout<<"\tROTATE AN ARRAY \n\n\n";

cout<<"\t____________________________________________________________\n\n\n";

cout<<"\tPlease specify the array you would like to rotate. \n\n\tEnter -999 at the end of the array.\n\n";

cout<>ArrO[Arrsize],cout<<"\n";

while(ArrO[Arrsize] != Sentinel)

{

Arrsize++;

cout<>ArrO[Arrsize],cout<<"\n";

}

cout<>Usershift,cout<<"\n";

//Computing Absolute Shift

AbsoluteShift = AbsolShiftfunc (Usershift , Arrsize);

//Computing Shift

for (int Counter = 0; Counter < Arrsize ; Counter++)

{

Destinationindex = IndivShiftfunc (Counter , AbsoluteShift, Arrsize);

ArrC[Destinationindex] = ArrO[Counter];

}

//Displaying Original and Rotated Array

cout<<"\t* Orginal Array:_\n\n\t";

cout<<"\t\t[";

for (int Counter = 0; Counter < Arrsize ; Counter++)

{

cout<<ArrO[Counter]<<",";

}

cout<<"]\n\n\n";

cout<<"\t* Rotated Array:_\n\n\t";

cout<<"\t\t[";

for (int Counter = 0; Counter < Arrsize ; Counter++)

{

cout<<ArrC[Counter]<<",";

}

cout<<"]\n\n";

cout<<"\t____________________________________________________________\n\n\n\t";

}

//_________________________________________________________//

void main()

{

Solution();

}

//_________________________________________________________//

PS : i am a begginner so please dont bash me

[…] “block swap” algorithms. Bentley also discusses a third algorithm, which he calls the “reversal” algorithm, and which we implemented several years ago. Bentley goes on to give timing comparisons […]