QUESTION

Let us have a set of n elements; the objective is to find all the possible permutations of this set. For example if we have a set of four elements viz. {a, b, c} then we need to print all the permutation of a, b and c as give below:\n\n1) { a, b, c}\n2) { a, c , b}\n3) { b, a, c}\n4) { b, c, a}\n5) { c, a, b}\n6) { c, b, a}\n\nClearly for a set of n elements there exists n! different permutations. One way to generate permutations is to iterate through n nested loops but that will be hardcoded approach as n may vary from time to time. So one flexible approach is to generate the permutation recursively. Let us have a set of three elements {a, b, c,} now to generate permutation follow these steps:\n\n1) Fix a and generate permutation of { b, c }\n2) Fix b and generate permutation of { a, c }\n3) Fix c and generate permutation of { a, b }\n.

ANSWER

#include<stdio.h>
#include<stdlib.h>
void permute(int* a,int k,int n);

int main()
{
 int i,n;
 int*a;
 scanf("%d",&n);
 a=(int*)calloc(n,sizeof(int));

        for(i=0;i<n;i++)
 scanf("%d",&a[i]);
 permute(a,0,n-1);
return 0;
}

void permute(int* a,int k,int n)
{ int i,t;
 if(k==n)
 {
  for(i=0;i<=n;i++)
  printf("%d ",a[i]);
  printf("\n");
 }else
 {
  for(i=k;i<=n;i++)
  { 
   t=a[k];
   a[k]=a[i];
   a[i]=t;
   permute(a,k+1,n);
   t=a[k];
   a[k]=a[i];
   a[i]=t;
  }
 }
}