To find all possible permutations of a given string.......

Question

Hi, This is just to work out a problem which looks pretty interesting. I tried to think over it, but couldn't find the way to solve this, in efficient time. May be my concepts are still building up... anyways the question is as follows..

Wanted to find out all possible permutation of a given string....... Also, share if there could be any possible variations to this problem.

I found out a solution on net, that uses recursion.. but that doesn't satisfies as it looks bit erroneous.

the program is as follows:-

void permute(char s[], int d)
{
   int i;

   if(d == strlen(s))
      printf("%s",s);

   else
   {
      for(i=d;i<strlen(s);i++)
      {
         swap(s[d],s[i]);
         permute(s,d+1);
         swap(s[d],s[i]);
      }
   }
}

If this program looks good (it is giving error when i ran it), then please provide a small example to understand this, as i am still developing recursion concepts..

Any other efficient algorithm, if exists, can also be discussed....

And Please,, this is not a HW........

Thanks.............

Answer 1

The code looks correct, though you only have the core of the algorithm, not a complete program. You'll have to provide the missing bits: headers, a main function, and a swap macro (you could make swap a function by calling it as swap(s, d, i)).

To understand the algorithm, it would be instructive to add some tracing output, say printf("permute(%s, %d)", s, d) at the beginning of the permute function, and run the program with a 3- or 4-character string.

The basic principle is that each recursive call to permute successively places each remaining element at position d; the element that was at position d is saved by putting it where the aforementioned remaining element was (i.e. the elements are swapped). For each placement, permute is called recursively to generate all desired substrings after the position d. So the top-level call (d=0) to permute successively tries all elements in position 0, second-level calls (d=1) try all elements in position 1 except for the one that's already in position 0, etc. The next-to-deepest calls (d=n-1) have a single element to try in the last position, and the deepest calls (d=n) print the resulting permutation.

The core algorithm requires Θ(n·n!) running time, which is the best possible since that's the size of the output. However this implementation is less efficient that it could be because it recomputes strlen(s) at every iteration, for a Θ(n²·n!) running time; the simple fix of precomputing the length would yield Θ(n·n!). The implementation requires Θ(n) memory, which is the best possible since that's the size of the input.

Answer 2

For an explanation of the recursion see Gilles answer.

Your code has some problems. First it will be hard to implement the required swap as a function in C, since C lacks the concept of call by reference. You could try to do this with a macro, but then you'd either have to use the exclusive-or trick to swap values in place, or use a temporary variable.

Then your repeated use of strlen on every recursion level blows up your complexity of the program. As you give it this is done at every iteration of every recursion level. Since your string even changes (because of the swaps) the compiler wouldn't even be able to notice that this is always the same. So he wouldn't be able to optimize anything. Searching for the terminating '\0' in your string would dominate all other instructions by far if you implement it like that.