Thread: Circular rotation pf string array

  1. #1
    Registered User
    Join Date
    Oct 2019
    Posts
    1

    Circular rotation pf string array

    Hi!

    I'm trying to write a function ('rotate') that rotates the first n elements of my string array arr by shift positions in the clockwise direction if shift is positiv (anti-clockwise if negativ shift).

    For example:
    For arr = "hello",
    shift = 2,
    n = 4,
    I'd like to obtain "llheo".

    My code:
    Code:
    
    void rotate(char *arr, int shift, int n) {
    if (shift >= 0){
      for (int j=0; j<= shift; j++){
        char tempfirst = arr[n-1];
        for (int i=n-1; i>0; i--){
          arr[i]=arr[i-1];
          arr[0]=tempfirst;
        }
      }
    }
    else {
      shift = -shift;
      for (int j=0; j<= shift; j++){
        char templast = arr[0];
        for (int i=0; i<(n-1); i++){
          arr[i]=arr[i+1];
          arr[n-1]=templast;
        }
      }
    }
    return;
    }
    
    Although there are no syntax errors, my code doesn't work.
    Thank you in advance!

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > arr[0]=tempfirst;
    These things should be outside your loops.
    You want to do them last, after you've moved the whole array.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Nov 2018
    Location
    Amberg in upper palatinate, Bavaria
    Posts
    66
    I'm trying to write a function ('rotate') that rotates the first n elements of my string array arr by shift positions in the clockwise direction if shift is positiv (anti-clockwise if negativ shift).

    May be you need some steps to develop this code.
    The first step could be like this below:
    Code:
    #include <stdio.h>
    #include <stdlib.h>  /* strncpy, EXIT_SUCCESS */
    #include <string.h>
    
    
    // copies a part of a string of zfolge from the sign 'beginn' including to 'ende' to the string  'erge*
    void STRITEIL(char *zfolge, char *erge, int beginn, int ende)
    {
      int laenge, lge = 0;
      
      lge = strlen(zfolge);
      laenge = (ende - beginn) + 1;
      
      if((beginn >= 0) && (beginn <= ende) && (ende < lge) && (laenge >= 1))
       {
        strncpy( erge, zfolge + beginn, laenge);
       }
    }
     
    // deletes a part of the string 'erge* from the sign 'beginn' including to 'ende' 
    void delstrpart(char *erge, int beginn, int ende)
    {
      int lge = 0, i, j;
      
      lge = strlen(erge);
      
      //printf("*erge: %s\n", erge);
      if((beginn >= 0) && (beginn <= ende) && (beginn < lge) && (ende <= lge))
      for (i = beginn; i <= ende; i++)
       {
        for (j = beginn; j < lge; j++)
         {
          erge[j] = erge[j + 1];       
          }
        //printf("*erge: %s\n", erge); 
       }      
      
    } 
     
     
    int main(int argc, char **argv)
    {
     char wort[] = "012345678901234567890";
     char erge[100] = {0};
     char stra[100] = {0};
     char strb[100] = {0};
     char strc[100] = {0};
     char strd[100] = {0};
     int lge = -1;
    
     lge = strlen(wort);
     
     // copy part of string
     printf("Word: %s\n", wort);
     STRITEIL(wort, erge, 7, 11);
     printf("est ergo: %s\n", erge);
     
     // deletes a part of a string
     printf("Word: %s\n", wort);
     strcpy(erge, wort);
     delstrpart(erge, 4, 6); 
     printf("est ergo: %s\n", erge);
     
     // moves part of a string (sings 4 to 6) 2 steps to the left side
     strcpy(erge, wort);
     STRITEIL(wort, strb, 4, 6); // to moved part
     delstrpart(erge, 4, 6);     // del moved part
     
     STRITEIL(wort, stra, 0, 2); // erster Teil 
     STRITEIL(wort, strd, 3, 4); // erster Teil 
     STRITEIL(wort, strc, 7, (lge -1)); // erster Teil 
     
     printf("deleted ergo: %s\n", erge);
     
     
     printf("%s %s %s %s\n", stra, strb, strd, strc);
     
     strcpy(erge, stra);
     strcat(erge, strb);
     strcat(erge, strd);
     strcat(erge, strc);
     
     printf("after moved erge: %s\n", erge);
     
     
     return EXIT_SUCCESS;
    }
    For some problems it is better to take first not the computer, but rather
    a paper and a pencil to determine coarse the way of proceeding.

  4. #4
    Registered User
    Join Date
    Nov 2018
    Location
    Amberg in upper palatinate, Bavaria
    Posts
    66
    A example who is better to understand is:
    Code:
    #include <stdio.h>
    #include <stdlib.h>  /* strncpy, EXIT_SUCCESS */
    #include <string.h>  /* strlen */
    
    
    // copies a part of a string of zfolge from the sign 'beginn' including to 'ende' to the string  'erge*
    void part_of_string(char zfolge[], char erge[], int beginn, int ende)
    {
      int laenge, lge = 0;
      
      lge = strlen(zfolge);
      laenge = (ende - beginn) + 1;
      
      if((beginn >= 0) && (beginn <= ende) && (ende < lge) && (laenge >= 1))
       {
        strncpy( erge, zfolge + beginn, laenge);
       }
    }
     
    // deletes a part of the string 'erge* from the sign 'beginn' including to 'ende' 
    void delstrpart(char erge[], int beginn, int ende)
    {
      int lge = 0, i, j;
      
      lge = strlen(erge);
      
      //printf("*erge: %s\n", erge);
      if((beginn >= 0) && (beginn <= ende) && (beginn < lge) && (ende <= lge))
      for (i = beginn; i <= ende; i++)
       {
        for (j = beginn; j < lge; j++)
         {
          erge[j] = erge[j + 1];       
          }
        //printf("*erge: %s\n", erge); 
       }      
      
    }
     
    
    // inserts the string 'ins' in string 'ziel' at position 'pos'
    void insstr(char ziel[], char ins[], int pos)
    {
      int lgz = 0, i, j, lgi, lge;
      
      lgz = strlen(ziel);
      lgi = strlen(ins);
      lge = lgz + lgi;
      
        //printf("laenge ziel ur: %d\n", lgz);
        //printf("laenge ziel ins: %d\n", lgi);
       //printf("neue laenge: %d\n", lge);
       // printf("ziel vorher : %s\n", ziel);
       
      for (i = lge; i >= pos; i--)
       {
        ziel[i] = ziel[i - lgi];
        //printf("ziel[i]: %c\n", ziel[i]); 
       }      
     
      j = 0;
      for (i = pos; i < pos + lgi ; i++)
       {
        ziel[i] = ins[j++];
        //printf("ziel[i]: %c\n", ziel[i]); 
       }      
     
    } 
     
    int main(int argc, char **argv)
    {
     char wort[] = "012345678901234567890";
     char erge[100] = {0};
     char strb[100] = {0};
     int lge = -1;
    
     lge = strlen(wort);
     
     // copy part of string
     printf("Word..........: %s\n", wort);
     printf("Word length...: %d\n", lge);
     part_of_string(wort, erge, 7, 11);
     printf("part of string: %s\n\n", erge);
     // ---------------End of first test-------------------
     
     // moves a part of a string
     strcpy(erge, wort);                   // copies string to edit
     printf("Word..........: %s\n", erge);
     part_of_string(wort, strb, 4, 6);     // copies the part of string to move from position 4 to 6
     printf("to delete.....: %s\n", strb);
     delstrpart(erge, 4, 6);               // deletes part of string to moded 
     printf("after delete..: %s\n", erge); // String after delete the part
     insstr(erge, strb, 1);                // inserts string 'strb' at position given by argument 3 (here 1) in string 'erge'
     printf("after insstr..: %s lge=%lu\n", erge, strlen(erge)); // shows the result 
     
     return EXIT_SUCCESS;
    }
     Circular rotation pf string array-screenshot_strotate1-jpg

  5. #5
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    Quote Originally Posted by rusyoldguy View Post
    A example who is better to understand is:
    <snip>
    I'm assuming that this is a student project so if it's not, please forgive me. But if it is, for student tasks like these the students are usually expected to not use library functions like strcpy (and if they are they're told which they're allowed to use; e.g. the task might say "no library functions to be used except strlen()". Also, I understand why you've used more than one array -- and the biggest reason I can think of is to avoid undefined behaviour of overlapping arrays when using strcpy and friends -- but I kind of have a gut feeling that the task wants them to do it in place, without secondary arrays. Without seeing the assignment description who knows though.

  6. #6
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    Quote Originally Posted by rusyoldguy View Post
    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).
    Last edited by Hodor; 10-20-2019 at 11:22 PM.

  7. #7
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    Well, I still can't find a good reference. However I did find this paper (https://pages.mtu.edu/~shene/PUBLICA...y-Rotation.pdf) (the paper is linked to from the Author's web page (Publications). I can't remember ever seeing that paper before but I do recall looking at early STL implementations so maybe I just copied the idea from there. Who knows. The paper is an interesting read anyway

  8. #8
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    For some reason I found this problem interesting so I did some more testing. I modified the gcd function to make it clearer (the new version might be faster but not significantly and the call to gcd() contributes nothing to overall execution time anyway). I also wrote another version of the loop method but replaced the inner loop with memmove() (cheating because I doubt a class assignment would allow calls to library functions). Then I tested them all using valgrind and different gcc optimisation levels.

    Code:
    ARRSIZE  90000000
    Shift    100
    
    compiler optimisation: none
        rotate_loops         126000000924    Incl. Cost: Ir
        rotate_memmove          914067971        Incl. Cost: Ir
        rotate_juggle          1890000854        Incl. Cost: Ir
        
    compiler optimisation: -O2
        rotate_loops          45000000221        Incl. Cost: Ir
        rotate_memmove          914068595        Incl. Cost: Ir
        rotate_juggle           990000528        Incl. Cost: Ir
        
    compiler optimisation: -O3
        rotate_loops            914064900        Incl. Cost: Ir
        rotate_memmove          914068595        Incl. Cost: Ir
        rotate_juggle           900000628        Incl. Cost: Ir
    Looking at the asm generated when using -O3 the code for the looping method is virtually identical to that using memmove (they both use memcpy actually but I can't use that function because of UB when there is overlapping areas of memory... the compiler can, and does, though). I would say that using a temporary array could improve speed even more (at the expense of increased memory usage obviously) because I could then move whole chunks like rusyoldguy, but my interest waned and I should be doing real work anyway. I also implemented the variation of the juggle method described in the aforementioned paper, but it makes basically no difference at all in my tests (probably because the call to gcd() is so insignificant). I'm quite impressed that when using -O3 that gcc replaced the inner loop with memcpy; pretty tricky. Of course these results are CPU/Instruction set dependent as well, but it was an interesting exercise, so *shrug*.

    Edit: I did not anticipate that using -O3 using gcc for my CPU would replace that inner loop with a very fast memory copy, so it was worth doing

    I should also add that for the tests I don't print the results like in the source code I provided in a previous post; that'd be silly

    Although maybe less meanginful than the Ir I compiled each version with no optimisation and took the average time of three runs (using the time command and with array size of 90000000 and a shift of 100 just like above)

    Code:
    rotate_loops:     16.862 seconds
    rotate_memmove:    0.635 seconds
    rotate_juggle:     0.693 seconds
    Last edited by Hodor; 10-21-2019 at 11:21 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with circular array of structures
    By 001bob in forum C Programming
    Replies: 2
    Last Post: 11-03-2011, 05:17 AM
  2. Rotation of elements of an array
    By drew99 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2011, 09:59 AM
  3. Circular array
    By Opel_Corsa in forum C++ Programming
    Replies: 5
    Last Post: 02-16-2006, 04:15 PM
  4. Circular array list
    By stimpyzu in forum C++ Programming
    Replies: 3
    Last Post: 03-07-2004, 02:28 PM
  5. array rotation?
    By ganja in forum C++ Programming
    Replies: 2
    Last Post: 01-23-2002, 07:34 PM

Tags for this Thread