Programming Forums

Programming Forums (http://www.programmingforums.org/forumindex.php)
-   C (http://www.programmingforums.org/forum60.html)
-   -   permutation recursion algorithm (http://www.programmingforums.org/showthread.php?t=13487)

gelareh_m Jul 6th, 2007 6:20 PM
permutation recursion algorithm
 
hi i can't undestand the last part of this code that is related to permutations of a set . if there's someone who can help me i'd be glad !


:
void perm(char *list , int i , int n)

/*generate all the permutations of list[i] to list[n] */

{
  int j,temp ;

  if(i == n) {

      for(j=0 ; j<=n ; j++)

        printf(" %c ", list[j]);

      printf("    ");

    }

    else {

      /* list[i]to list[n] has more than one permutation , generate these recursively */

      for(j=i ; j<=n ; j++) {

        swap(list[i],list[j],temp);
        perm(list,i+1,n);
        swap(list[i],list[j],temp);

          }
      }

}

mackenga Jul 10th, 2007 7:16 PM
Hmm, I think you're not getting your head around the recursion thing here. The idea is that the first part of the if statement is the 'base case' and the second is the 'recursive case'. With recursion, generally the base case is the simplest case, to which other cases can be reduced by repeatedly doing the recurse step. I haven't stared at the code above for long enough to give you a blow by blow account of how it works but a traditional example of a simpler recursive algorithm might help:

:
long int factorial(long int n)
{
  return (n - 1 ? factorial(n - 1) * n : 1);
}

Here, n = 1 is the base case; factorial of 1 is 1, which is easy. Factorial of anything bigger is that number n times the factorial of n-1, which will tend towards the base case of n = 1 so you know that a function defined that way will not recurse infinitely.

The problem being solved by the code you posted is a little more complicated; the idea is that if you want to find all the permutations of a string of items (like numbers for example) then all the permutations of each subset will be useful, and all the permutations of a list with 1 item are just that one item (there's only one permutation of such a list) so there's a base case to approach. Like I say I haven't thought it through properly but I can see that it suits a recursive solution. Just to add to the fun the recursive function you posted returns void - actually, all the recursive calls are sharing the same buffer via the pointer they're passed!

Well, I suggest you 'dry-run' this. Scribble your variables (buffers etc.) on a piece of paper then trace the execution through, remembering where to return to from each call to perm() of course! - this should clear it up. I can't be bothered to be honest! :)


All times are GMT -5. The time now is 2:31 AM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC