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?

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

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.

Compare your algorithm with this.