All Permutations

All Permutations of a Set of Elements

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:

1)      { a, b, c}

2)      { a, c , b}

3)      { b, a, c}

4)      { b, c, a}

5)      { c, a, b}

6)      { c, b, a}

Clearly 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:

1) Fix a and generate permutation of { b, c }
2) Fix b and generate permutation of { a, c }
3) Fix c and generate permutation of { a, b }

The pseudo code for the recursive algorithm to generate all permutation is as below:

permute(a,k,n)
{
 if(k==n) then print a[1..n]     // output permutation
 else
  for i=k to n do
  {
   t=a[k];a[k]=a[i]; a[i]=t;
   permute(a,k+1,n); // all permutation of a[k+1..n]
   t=a[k];a[k]=a[i]; a[i]=t;
  }
}

The calling function takes inputs and calls permute function passing three arguments a list of elements, start index and end index.

Inside permute it is checked whether start index and end index are same (if there is only one element) or not. If both are same then print the permutation else iterate through for loop and call permute function recursively.

The following program implements this pseudo code in C :

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

void 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);
}

void permute(int* a,int k,int n)
{ int i,t;
 if(k==n)
 {
  for(i=0;i<=n;i++)
  printf("%d\t",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;
  }
 }
}

The output of the following program is as shown below:

Let us observe the output one by one:

The first line of input 3 is the number of elements to be entered y the user.

The second line of input consists of three input numbers 1, 2 and 3.

The remaining 6 lines are all permutations of the input elements i. e. all permutations of 1, 2 and 3.

Main function call permute function passing a, 0 and 2 as parameters.

First Call

Inside permute if condition is false hence else is executed. In else since i=0 and k=0 so no swapping. Here we have k=0, i=0 and  a[0]=1,a[1]=2 and a[2]=3. Now call again permute passing a, k+1(=1) and n(=2) as parameters.

Second Call

The value of  k and n differs so again else is executed. Inside else value of k and I is same so no swapping occurs hence i=1,k=1 and a[0]=1, a[1]=2 and a[2]=3. Call again permute function passing a, k+1(=2) and n(=2) as parameters.

Third Call

The value of k and n are same i.e. 2 hence if is executed and inside if content of list a is printed i. e. 1 2 3.

 Now control is transferred back to calling function i. e. to Second Call

[Third Call ends here]

Inside second Call again swap occurs. But i=1 and k=1 so actually no swapping. Again i is incremented by 1 hence value of i=2 and k=1 so swapping occurs i. e.  now a becomes a[0]=1, a[1]3 and a[2]=2 and now call permute passing a, k+1(=2) and n(=2) as parameters.

Fourth Call

The value of k and n are same i.e. 2 hence if is executed and inside if content of list a is printed i. e. 1 3 2.

 Now control is transferred back to calling function i. e. to Second Call

[Fourth Call ends here]

Inside second call swapping occurs as value of i=2 and k=1 so a[0]=1,a[1]=2 and a[2]=3. i is incremented by 1 and for condition becomes false hence control is transferred back to calling function i.e. First Call.

[Second call ends here]

Inside First Call Value of i and k are 0 hence again no swapping. Now i is incremented by 1 and it becomes 1. Now swapping occurs as i=1 and k=0. Hence revised list a is as a[0]=2, a[1]=1 and a[2]=3. And now call again permute  function passing a, k+1(=1) and n(=2) as parameters.

 Hence now again Second Call, Third Call and Fourth Call is repeated and following gets printed i.e. 2 1 3 and 2 3 1 and values of list a are a[0]=2, a[1]=1 and a[2]=3.

Again inside First Call swapping occurs as i=1 and k=0 and list a becomes a[0]=1, a[1]=2 and a[2]=3. 

Now i is incremented by 1 i. e. i becomes 2 now and k is 0  hence swapping occurs i. e. a[0]=[3] and a[1]=2 and a[2]=2 and  permute function is called passing a, k+1(=1) and n(=2) as parameters. Hence now again Second call Third Call and Fourth Call is repeated and following gets printed i. e. 3 2 1 and 3 1 2.

Again inside First call values are swapped and values of list a are a[0]=1, a[1]=2 and a[2]=3

[First Call ends here]

Hence values of list a remains intact after the completion of all recursive calls and all permutations are printed.