Re: how to rotate an array
From: Siemel Naran (SiemelNaran_at_REMOVE.att.net)
Date: 03/21/04
- Next message: Siemel Naran: "spaghetti code"
- Previous message: Todd: "Re: Comparing strings character by character and incrementing a value by one if they are equal."
- In reply to: Nikolai Borissov: "Re: how to rotate an array"
- Next in thread: Nikolai Borissov: "Re: how to rotate an array"
- Reply: Nikolai Borissov: "Re: how to rotate an array"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Sat, 20 Mar 2004 23:28:31 GMT
"Nikolai Borissov" <date4cpp@sympatico.ca> wrote in message
news:1Fz6c.30229$E71.1829457@news20.bellglobal.com...
> int array_rotation(char* arr, int arr_size, int rot)
> {
> // Parameter check
> if(!(arr&&arr_size>0))
> return -1;
>
> // Normalization of rotation value
> rot = rot%arr_size;
> rot = rot<0?rot+arr_size:rot;
>
> // Rotation
> if(rot!=0)
> { int gcd; // greatest common divisor
> { int n=arr_size,m=rot;
> while((gcd=n%m)&&(n=m%gcd)&&(m=gcd%n));
> gcd = gcd ? n ? n : gcd : m;
> }
> int mvs = arr_size/gcd;
> while(gcd--)
> { int ind = gcd;
> char c = arr[ind];
> int i = mvs;
> while(--i) { int ind_prev = ind;
> if( (ind+=rot) >= arr_size )
> ind-=arr_size;
> arr[ind_prev] = arr[ind];
> }
> arr[ind] = c;
> }
> }
> return 0;
> }
What's going on with the gcd part? Also, without parenthesis it's hard to
read
> gcd = gcd ? n ? n : gcd : m;
What is the running time of the above algorithm? Your algorithm looks
correct for arr_size is 0 or 1.
Here's my attempt. Consider ABCDEF which have to shift right two notches to
EFABCD. Start with ABCDEF. It has length 6. Start at array[0]. Copy
array[0] into array[2] to yield ABADEF. Copy the old character at array[2]
to array[4] to yield ABADCF. Copy the old character at array[4] to
array[6], but array[6] should be array[0] to yield EBADCF. We're back where
we started, so we're done with this series of 0-2-4. Now go on to series
1-3-5 and repeat. Copy array[1] to array[3] to yield EBABCF. Copy the old
character at array[3] to array[5] to yield EBABCD. Copy the old character
at array[5] to array[7] which is array[1] to yield EFABCD. We're back where
we started and completed both series and performed 6 copies, so we're done.
It may not be the most efficient algorithm.
There will be an outer loop that loops through the number of series, in our
example 2 series 0-2-4-0 and 1-3-5-1. There will be an inner loop that
loops through the number of elements in the series, so for the 1st series
0-2-4-0 it loops through 0 then 2 then 4 then 0.
Algorithmically, the outer loop 'series' is from [0, infinity); and the
inner loop 'indx' starts at 'series', then increments 'indx' by 'shift'
until we reach the 'series'. So for series=0 we'll have in the inner loop
indx=0,2,4,0 and it copies char[0] to char[2], char[2] to char[4], char[4]
to char[6 or 0] for a total of 3 copies. As we have not performed size=6
copies we still have some more work to do. Now increment series and repeat.
So for series=1 we'll have in the inner loop indx=1,3,5,1 and it copies
char[1] to char[3], char[3] to char[5], char[5] to char[7 or 1] for a total
of 3 copies. As we have performed size=6 copies we're all done. Variable
'j' counts the number of copies performed, so when 'j' equals 'size' we're
done.
Furthermore, in the inner loop where for example we copy char[1] to char[3],
char[3] to char[5], char[5] to char[7 or 1] there is a danger that we run
past the bounds of the array as in char[7] whereas the array has length 6.
We can solve this by guarding each increment of 'indx' with modulo, so
instead of indx+=shift we have to say indx=(indx+shift)%size, as you do
above. But for the first few copies like char[1] to char[3], char[3] to
char[5], we don't need the check, and index+=shift will suffice, and could
yield better performance.
So as an optimization we pre-compute the number of copies 'within' we can do
without running past the end of the array. Consider the series 1-3-5-1
where series=1. We start at indx=1, and after 'within' increments pass the
end of the array, so indx+within*shift>=size, for which
within>=(size-indx)/shift. In our example, for indx=1 and size=6 and
shift=2, within>=2.5; which means we can only perform 2 copies before
running past the end of the array. For the series 0-2-4-0 for which
series=0 things are more complicated. We have within>=3, and note that
within is exactly equal to 3, which means 3 copies from char[0] to char[2],
char[2] to char[4], char[4] to char[6]. But the last copy from char[4] to
char[6] runs past the end of the array too. So we ought to perform only 2
copies. In other words, if 'within' has no fractional part then it means
we'll eventually hit the one-past-end element of the array and so we should
decrease 'within' by 1.
I ran a few tests, but there may be sideline test cases for which my
algorithm fails.
#if defined(__BORLANDC__)
#include <vcl.h>
#endif
#include <cstdio>
#include <iterator>
template <class Iter>
void rotate(
const Iter begin,
const Iter end,
typename std::iterator_traits<Iter>::difference_type shift
)
{
using std::swap;
typedef typename std::iterator_traits<Iter>::difference_type Int ;
typedef typename std::iterator_traits<Iter>::value_type Value;
const Int size = end-begin;
if (!size) return;
shift %= size;
if (!shift) return;
if (shift<0) shift = size+shift;
Int series = 0;
Int j = 0;
Iter seriesbegin = begin;
while (true)
{
Iter iter = seriesbegin;
Int indx = series;
Value value = *iter;
while (true)
{
const Int diff = size-indx;
const bool exact = bool(!(diff%shift));
const Int within = diff/shift;
for (Int k=exact; k<within; ++k)
{
iter += shift;
indx += shift;
swap(*iter, value);
++j;
}
indx = (indx+shift)%size;
iter = begin+indx;
swap(*iter, value);
++j;
if (indx == series) break;
}
if (j==size) break;
++series;
++seriesbegin;
}
}
int main(int argc, char * * argv)
{
using std::printf;
const char originalarray[] = "ABCDEF";
const int length = sizeof(originalarray)-1;
for (int r=-length; r<=length*2; ++r)
{
char array[length+1];
std::strcpy(array, originalarray);
printf("%s\n", array);
printf("rotate=%d\n", r);
rotate(array, array+length, r);
printf("%s\n", array);
printf("\n");
}
}
- Next message: Siemel Naran: "spaghetti code"
- Previous message: Todd: "Re: Comparing strings character by character and incrementing a value by one if they are equal."
- In reply to: Nikolai Borissov: "Re: how to rotate an array"
- Next in thread: Nikolai Borissov: "Re: how to rotate an array"
- Reply: Nikolai Borissov: "Re: how to rotate an array"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
