Programming Forums > Application Development > C

gelareh_m · Jul 6th, 2007, 5:20 PM

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 !

(Toggle Plain Text)

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, 6: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:

(Toggle Plain Text)

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!

Jul 6th, 2007, 5:20 PM	#1
gelareh_m Newbie Join Date: Jul 2007 Location: iran Posts: 4 Rep Power: 0	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 ! (Toggle Plain Text) 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); } } } 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); } } }

Jul 10th, 2007, 6:16 PM	#2
mackenga Professional Programmer Join Date: Mar 2005 Location: Glasgow, Scotland Posts: 317 Rep Power: 4	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: (Toggle Plain Text) long int factorial(long int n) { return (n - 1 ? factorial(n - 1) * n : 1); } 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! __________________ "I'm not a genius. Why do I have to suffer?"

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Permutation	Mcoy	C++	5	Mar 15th, 2006 3:22 AM
Recursion and Scheme	Jessehk	Coder's Corner Lounge	8	Feb 4th, 2006 7:46 AM
Debug recursion method()	pr0gm3r	Java	3	Oct 11th, 2005 12:33 PM
Recursion	Mjordan2nd	Coder's Corner Lounge	22	Jul 7th, 2005 11:26 AM
Permutation Program	Mad_guy	Assembly	11	Jun 8th, 2005 3:36 AM

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C

permutation recursion algorithm