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 }
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.
No comments :
Post a Comment