Thread: Prmutations

  1. #1
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278

    Prmutations

    I have the following algorithm for listing permutations but i cannot properly implement in C program:-

    Code:
    Algorithm Perm(a,k,n)
    {
        if (k = n) then write (a[1:n]); // output permutation
        else // a[k:n] has more than one permutation
                 //  Generate these recursively
                 for i := k to n do
                 {
                        t := a[k]; a[k] := a[i]; a[i] := t;
                        Perm(a,k+1,n);
                        // All permutations of a[k+1:n]
                        t := a[k]; a[k] := a[i]; a[i] := t;  
                  }
    }
    I have coded the following but it does not work:-

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    void Perm(char[],unsigned,unsigned);
    
    void Perm(char a[],unsigned k,unsigned n)
    {
         if(k == n-1)
    	   printf("%s\n",a);
         else
         {
          	   for(unsigned i = k;i < n;i++)
    	   {
    	           char t = a[k]; a[k] = a[i]; a[i] = t;
    		   Perm(a,k+1,n-1); 
    		   t = a[k]; a[k] = a[i]; a[i] = t;
     	   }
         }  
    }
    
    int main(void)
    {
             unsigned n;
    	 char *a;
    	 
    	 printf("Enter the size of the number : ");
    	 scanf("%u",&n);
    	 
    	 a = (char*)malloc(n*sizeof(char));
    	 
    	 printf("\nEnter the number : ");
    	 scanf("%s",a);
    	 	    
    	 Perm(a,0,n-1);
    	 
    	 system("pause");
    	 return 0;
    }

  2. #2
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    Mostly, you have a problem with off by 1s.

    Your biggest mistake is here

    Code:
    Perm(a,k+1,n-1);
    In particular, you are decreasing n each recursive call, but n itself is supposed to be the length of a, but the length of a is unchanged. Otherwise, there are two more off by 1s, but you should be able to figure it out by just trying small example cases, like permuting the first 3 numbers.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

Popular pages Recent additions subscribe to a feed