Thomas W. Christopher | Consulting in High Performance Computing. Training in Concurrency, Networking, and Parallelism, especially in Python and Java. |
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).
Rotation by reversalsThe first method is based on reversal. If x^{R} is the reversal of string x, then vu is (u^{R} v^{R})^{R}. The elements in a section of an array can be easily reversed by starting off a pointer at each end, exchanging the elements they point to, and moving the pointers toward the center until the pointers meet. The code to rotate [0,mid) and [mid,N) is:
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); |
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++; }
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:
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|).
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; }
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; }