Rotate An Array
October 12, 2010
Today’s exercise is simple but tricky: write a function to rotate the elements of an array. The function takes two arguments: the array to be rotated and the number of elements to rotate, where a positive count rotates to the left and a negative count rotates to the right. For instance, given the array [1 2 3 4 5 6], a rotation of 2 to the left gives [3 4 5 6 1 2], and a further rotation of 2 to the right restores the original array.
You should be sure to handle the edge cases properly. If the count is zero or the length of the array, the array should remain unchanged. If the count is greater than the length of the array, you should still do the right thing; for instance, a rotation of 8 on the array given above gives [3 4 5 6 1 2], the same as a rotation of 2.
Your task is to write the rotate function described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
[…] 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 […]