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.
Pages: 1 2
[…] 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:
def rotate(array, nelts): n = nelts % len(array) return array[n:] + array[:n]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).
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; };; 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 Implementation
My 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#.
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; }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
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 […]