Originally Posted by
rusyoldguy
A example who is better to understand
Ok, since you've provided code I decided I'd provide some as well. I haven't really tested either of these extensively but I think they're ok.
Attempt 1 (the obvious way)
Code:
#include <stdio.h>
#include <assert.h>
void rotate(char *arr, int shift, int n);
void print_array(const char *arr, int n);
int main(void)
{
char arr[] = {'h', 'e', 'l', 'l', 'o'};
print_array(arr, sizeof arr / sizeof arr[0]);
rotate(arr, 2, 4);
print_array(arr, sizeof arr / sizeof arr[0]);
return 0;
}
void rotate(char *arr, int shift, int n)
{
int i, j;
char tmp;
/* The calling function is responsble for making sure that arr != NULL */
assert (arr != NULL);
/* Return early if the calling function is being silly
* i.e. rotating 0 or 1 characters of the sequence makes no sense because the result
* would be the same as no rotatation at all for any value of 'shift'
*/
if (n < 2)
return;
/* No point rotating more than we need to so limit shift. This line can be omitted if
* you don't mind the loops iterating more than they need to; the result will be the same
*/
shift %= n;
if (shift < 0) { /* Rotate anti-clockwise (to the left) */
shift = -shift;
for (i = 0; i < shift; ++i) {
tmp = arr[0];
for (j = 0; j < n - 1; ++j)
arr[j] = arr[j + 1];
arr[j] = tmp;
}
} else { /* Rotate clockwise (to the right) */
for (i = 0; i < shift; ++i) {
tmp = arr[n - 1];
for (j = n - 1; j > 0; --j)
arr[j] = arr[j - 1];
arr[j] = tmp;
}
}
}
void print_array(const char *arr, int n)
{
int i;
for (i = 0; i < n; i++)
printf("%c", arr[i]);
printf("\n");
}
Attempt 2 (a probably more efficient way, at least in theory)
Code:
#include <stdio.h>
#include <assert.h>
void rotate(char *arr, int shift, int n);
static void rotate_left(char *arr, int shift, int n);
static void rotate_right(char *arr, int shift, int n);
void print_array(const char *arr, int n);
int gcd(int a, int b);
int main(void)
{
char arr[] = {'h', 'e', 'l', 'l', 'o'};
print_array(arr, sizeof arr / sizeof arr[0]);
rotate(arr, 2, 4);
print_array(arr, sizeof arr / sizeof arr[0]);
return 0;
}
void rotate(char *arr, int shift, int n)
{
int i, j, k;
char tmp;
/* The calling function is responsble for making sure that arr != NULL */
assert (arr != NULL);
/* Return early if the calling function is being silly
* i.e. rotating 0 or 1 characters of the sequence makes no sense because the result
* would be the same as no rotatation at all for any value of 'shift'
*/
if (n < 2)
return;
/* No point rotating more than we need to so limit shift. This line can be omitted if
* you don't mind the loops iterating more than they need to; the result will be the same
*/
shift %= n;
if (shift < 0)
rotate_left(arr, -shift, n);
else
rotate_right(arr, shift, n);
}
/*========================================================================*/
/* See "juggling algorithm" */
static void rotate_left(char *arr, int shift, int n)
{
int i, j, k;
int g_cd;
char tmp;
g_cd = gcd(shift, n);
for (i = 0; i < g_cd; i++) {
tmp = arr[i];
j = i;
while (1) {
k = j + shift;
if (k >= n)
k -= n;
if (k == i)
break;
arr[j] = arr[k];
j = k;
}
arr[j] = tmp;
}
}
static void rotate_right(char *arr, int shift, int n)
{
int i, j, k;
int g_cd;
char tmp;
g_cd = gcd(shift, n);
for (i = 0; i < g_cd; i++) {
tmp = arr[i];
j = i;
while (1) {
k = j - shift;
if (k < 0)
k += n;
if (k == i)
break;
arr[j] = arr[k];
j = k;
}
arr[j] = tmp;
}
}
/*========================================================================*/
int gcd(int a, int b)
{
if (a < 0)
a = -a;
if (b < 0)
b = -b;
if (b) {
while ((a %= b) && (b %= a))
;
}
return a + b;
}
void print_array(const char *arr, int n)
{
int i;
for (i = 0; i < n; i++)
printf("%c", arr[i]);
printf("\n");
}
-----
Additional comments below (this is the reason for the edit)
If I use this for main (using the second implementation above):
Code:
int main(void)
{
char arr[] = "012345678901234567890";
print_array(arr, 21);
rotate(arr, 7, 11);
print_array(arr, 21);
print_array(arr, 11);
return 0;
}
I get as output:
Code:
012345678901234567890
456789001231234567890
45678900123
This is slightly different to what you provide as output. So one of us has something wrong. The output of my program looks right, but perhaps I'm missing something (maybe missing enough beer)
-------
Edit 2: If anyone has more information on the juggling algorithm implemented, please let me know. Writing it down on paper I can understand how it works and I recall first using it (or a very similar variant) around about the year 2000. The datestamp on my archive for the implementation is for the year 2000 anyway, but the problem is I think the datestamp reflects the date I restored from a backup and not when I wrote the original program. I can't recall where I came across the algorithm (I doubt I derived it myself). I've just looked through Knuth (TAOCP) and can't really see it mentioned so I don't think it's from there. But TAOCP, especially back in 2000, is my first call for algorithms and I can't think of where else I may have come across it. Unfortunately I don't have a comment in the original code referencing where the algorithm comes from (ugh).