Thomas W. Christopher

Consulting in High Performance Computing. Training in Concurrency, Networking, and Parallelism, especially in Python and Java.

Rotation of arrays

Thomas W. Christopher

Problem

The problem is to perform an in-place rotation of a one-dimensional array.

In out discussions, we will view the array using notation developed to talk about strings. We will use letters near the end of the alphabet represent strings, and by extension, sections of arrays. We let |x| represent the length of a string. Rotation means the following: Given the string, uv, where u and v are strings, we wish to transform them to the string vu without using any more than a tiny, fixed amount of additional storage (e.g. one variable).

setColor(mid,Color.red);
int i,j;
for (i=0,j=mid-1;i<j;i++,j--)
	exchange(i,j);
for (i=mid,j=N-1;i<j;i++,j--)
	exchange(i,j);
for (i=0,j=N-1;i<j;i++,j--)
	exchange(i,j);

Rotate2 Rotation by exchanges of sequences

A second method is based on exchanging the values in subarrays. The values in two equal-length subarrays can be exchanged by passing a pointer upwards through each subarray, exchanging the values they point to.

To rotate the string uv, there are four cases:

(1) If either |u|=0 or |v|=0, no rotation is necessary.

(2) If |u|=|v|, then the two strings may be exchanged yielding vu.

(3) If |u|>|v|, let u=wx where |v|=|w|. Thus uv=wxv and vu=vwx. Exchange the sequences v and w in wxv giving vxw. Now rotate the string xw.

(4) If |u|<|v|, let v=yz where |u|=|y|. String uv=uyz and vu=yzu. Exchange the sequences u and y in uyz giving yuz. Now rotate the string uz.

Cases (3) and (4) imply a recursive call of rotate for smaller sub arrays. Since this is a tail-end call, it can be handled by a loop. Cases (3) and (4) do not require calculating the sizes |u| and |v| before hand. You simply starts exchanging the sequences u and v, remembering the beginning position of v. If you fall off the end of v first, if was an instance of case (3). If you bump into the biginning of v first, it was in instance of case (4). If both happen simultaneously, it was case (2).

Here's the code used in the Applet:

setColor(mid,Color.red); 
int i,j;
i=0;j=mid;
while (i<N){
	if (j==N) j=mid;
	if (i==j) break;
	if (i==mid) {
		setColor(mid,Color.blue);
		mid=j;
		setColor(mid,Color.red);
	}
	exchange(i,j);
	i++;
	j++;
}

Rotate3 Permutation group

The permutation group approach involves figuring for a position, where the value that will fill it will come from, and where the value that will fill that position will come from, and so on.

These values will be shifted around a cycle. What we do is find the lowest numbered array element in each cycle and shift all elements in the cycle to their new locations.

So there are two problems:

1. Where will the value come from that will end up at a particular index? Answer: The value that will end up in position i will come from (i+|u|)mod(|u|+|v|).

2. How do we recognize when index i is the lowest index in a cycle? We first follow the cycle from i until we come to an index j<=i. If j=i, i is the lowest index in its cycle. If j<i, i obviously is not.

The Applet uses this code to calculate the location of the predecessor in the cycle:

int pred(int i,int mid,int N){return (i+mid)%N;}

The code to do the actual rotate is:

setColor(mid,Color.red); 
int i,j,k, stillToMove;
for (i=0,stillToMove=N; stillToMove>0 /*&& i<N*/; i++) {
    for (j=pred(i,mid,N);j>i;j=pred(j,mid,N));
    if (j<i) continue;
    for (k=i,j=pred(i,mid,N);j!=i;k=j,j=pred(j,mid,N)) {
        exchange(k,j);
        --stillToMove;
    }
    --stillToMove;
}

Rotate3 In-place matrix transpose

The same technique that is used for rotation by permutation groups can be used to perform an in-place transpose of a matrix. Suppose we have an LxM matrix A in row major order with zero origin addressing. the location of element A[i,j] will be at offset i*M+j elements from the beginning of the array. Of course 0<=i<L and 0<=j<M.

Each position k, 0<=k<L*M, corresponds to a unique pair of i and j values:

• i=k/M

• j=k%M  where, as in Java, % is the modulus operator.

The transposed array A', A'[j,i]=A[i,j]. Element A'[j,i] will be at offset j*L+i. Similarly, position k', 0<=k'<L*M, corresponding to element A'[j,i], yields j=k'/L and i=k'%L.

For a matrix transpose, the index of a predecessor in the permutation group for location k is computed by

int pred(int k,int L,int M){return (k%M)*L+k/M;}

The code to do the transpose is:

int LxM=L*M;
int i,j,k, stillToMove;
for (i=0,stillToMove=LxM; stillToMove>0; i++) {
    for (j=pred(i,L,M);j>i;j=pred(j,L,M));
    if (j<i) continue;
    for (k=i,j=pred(i,L,M);j!=i;k=j,j=pred(j,L,M)) {
        exchange(k,j);
        --stillToMove;
    }
    --stillToMove;
}