string permutation problem

This is a discussion on string permutation problem within the C Programming forums, part of the General Programming Boards category; I'm trying to write a simple string permutation program. The program takes a string and displays all permutations of the ...

  1. #1
    Registered User
    Join Date
    Oct 2005
    Posts
    10

    string permutation problem

    I'm trying to write a simple string permutation program. The program takes a string and displays all permutations of the string. However, the code needs a little debug, and I'm out of patience. I've worked on this faaar too long. Can anyone find the problem.

    The function that does the work is called perm().
    Here's perm():

    Code:
    void perm(char* str, int n, int len){
      int i,k,j;
      char* tmp, ch; 
    
      tmp = malloc((len+1) * sizeof(char));
      if(!tmp){
        puts("\ncall to malloc() failed.");
        exit(1);
      }
    
      strcpy(tmp, str);
    
      for(i=0; i<len; i++){
    
        //rotate string i times, so next letter is first in line.
        for(j=0; j<i; j++){
          ch = tmp[0];
          for(k=0; k<len-1; k++) tmp[k] = tmp[k+1];
          tmp[len-1] = ch;
          tmp[len] = '\0';
        }
        A[n] = tmp[0];
        for(j=0; j<len; j++) tmp[j] = tmp[j+1];
        if(n<len) perm(tmp, n+1, len-1);
        else{
          A[n+1] = tmp[0];
          printf("\npermy: %s", A);
        }
      }
    }
    A[] is global and contains each permutation of str. perm() is called the first time like this:

    Code:
    perm(str, 0, len);
    where str is a pointer to a string of length len.

    The problem is the same as always, I've overstepped an array somewhere. I've run out of patience. Can you find the problem?
    Last edited by Korg; 10-07-2005 at 03:58 AM. Reason: update

  2. #2
    ZuK
    ZuK is offline
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    Quote Originally Posted by Korg
    where str is a pointer to a string of length len.
    So the problem is here
    Code:
      tmp = malloc(len * sizeof(char));  // you should allocate len+1 chars to have space for the terminating \0
      if(!tmp){
        puts("\ncall to malloc() failed.");
        exit(1);
      }
      strcpy(tmp, str); // this will copy len+1 chars
    Kurt

  3. #3
    Registered User
    Join Date
    Oct 2005
    Posts
    10

    Still unsolved.

    Yes you're right. That was one of the problems. Bit of a misunderstanding with my string length. I've updated my code above with the change to the malloc() call and also a couple of changes with for loop conditions.

    However, the problem still stands. Run it for yourself and you'll get the idea.

    I'm going to work on it today, but it would be interesting to see if you can solve it before I can.

  4. #4
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Compare your algorithm with this.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. string problem
    By INeedSleep in forum C++ Programming
    Replies: 24
    Last Post: 11-08-2007, 10:52 PM
  2. Custom String class gives problem with another prog.
    By I BLcK I in forum C++ Programming
    Replies: 1
    Last Post: 12-18-2006, 02:40 AM
  3. Message class ** Need help befor 12am tonight**
    By TransformedBG in forum C++ Programming
    Replies: 1
    Last Post: 11-29-2006, 10:03 PM
  4. Replies: 4
    Last Post: 03-03-2006, 01:11 AM
  5. Classes inheretance problem...
    By NANO in forum C++ Programming
    Replies: 12
    Last Post: 12-09-2002, 02:23 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21