Sunday, September 14, 2008

Rotating an array

Over at polymathprogrammer there is an article about rotating an array, which was a response to Mr Chen's entry on an interview question

Reading the answers got me thinking as I had recently written a roate method in order in implement tic-tac-toe (don't ask why). My solution then had been along the lines of one of the suggested solutions:


for (int y = 0; y < n; y++)
for (int x = 0; x < n; x++)
output[n - y - 1,x] = input[x,y];


though I used a mapping intead of a direct move.

What was interesting was that someone else had suggested that you could just do it using two mirror operations (mirror horizontal and then a diagonal) which was a very elegant way of doing it.

I liked this and it made me think was there another way to do it (as in how many ways can this problem be solved. And I came up with this, which takes advantage of using a single dimension array for holding two dimensional data:


1 &124; 2 &124; 3
-----------
4 &124; 5 &124; 6
-----------
7 &124; 8 &124; 9


stored as


int[] array = new int[] { 1, 2, 3, 4 , 5, 6, 7, 8, 9};


which if rotated looks likes:


int[] array = new int[] { 7, 4, 1, 8, 5, 2, 9, 6, 3};


which looks like the mapping:


destinationOffset += w;
if (destinationOffset > l)
destinationOffset = destinationOffset % w;


in effect, offset its new position by the width of the matrix (3) and wrap overflows back to the start. This looked good until number 4 as it collided with 1, so I just moved it back a step if it collided. Problem solved for 90° right:

gives:


7 &124; 4 &124; 1
-----------
8 &124; 5 &124; 2
-----------
9 &124; 6 &124; 3


Now you could just apply the function multiple times for 180°, 270° rotations, but looking at the resultant arrays shows two things:
180°: results is the original array in reverse order
270°: results is the 90° array in reverse order

So it looks like reversing an array is the same as a diagonal mirror! which means you need just two functions, a rotate and an array reverse (which is part of most array implementations, .Net as Arrray.Reverse)

Code for just the single rotation is:


int size = 3*3;
int[] array = new int[size];
for (int i = 0; i < size; i++)
array[i] = i + 1;

int l = array.Length;
int w = (int)Math.Sqrt(array.Length);

int[] destination = Rotate(array, l, w);


private static int[] Rotate(int[] array, int l, int w)
{
int[] destination = new int[l];
int destinationOffset = -1;
for (int sourceOffset = 0; sourceOffset < l; sourceOffset++)
{
destinationOffset += w;

// wrap around
if (destinationOffset > l)
{
destinationOffset %= w;
// collision avoidance
destinationOffset--;
}

destination[destinationOffset] = array[sourceOffset];

}

return destination;
}


and of course given we know the size of the array, and we can use XOR to do swaps in place

swap(a, b) =>
a = a ^ b; // a^= b;
b = b ^ a; // b ^= a;
a = a ^ b; // a ^= b;


then the fast version (without working at a bit level) might be:


private static void RotateInPlace4by4(int[] array)
{
// corners (1,4 moves around)
swap(ref array[3], ref array[15]);
swap(ref array[0], ref array[3]);
swap(ref array[0], ref array[12]);

// left inner (2 moves around)
swap(ref array[7], ref array[14]);
swap(ref array[1], ref array[7]);
swap(ref array[1], ref array[8]);

// right inner (3 moves around)
swap(ref array[11], ref array[13]);
swap(ref array[2], ref array[11]);
swap(ref array[2], ref array[4]);

// middle square (6,7,10,11)
swap(ref array[5], ref array[9]);
swap(ref array[6], ref array[10]);
swap(ref array[6], ref array[9]);
}

private static void swap(ref int a, ref int b)
{
a ^= b;
b ^= a;
a ^= b;
}

1 comment:

fe said...

if you are looking to shift or rotate a single dimension array see the post on http://blog.figmentengine.com/2008/10/rotating-string.html