/*A recursive function to compute all the permutations of a set of numbers
of size n
*/

#include <stdio.h>

void swap(int a[],int x,int y)
{   int temp;
	temp=a[x];
	a[x]=a[y];
	a[y]=temp;
}

void permute(int a[],int f,int n)
{
	int i,j,k;
    //Terminating condition : till the last 2 variables of the arrays are swapped
	if(n-f>1)
	{   //loop that brings all integers to the first position in the array
		for(j=0;j<n-f;j++)
		{
			if(j)
				swap(a,f,f+j);//bringing f+j th element to the first position of the sub array ie fth position.   
			permute(a,f+1,n);//calling the function recursively with the remaining array ie the array starting from f+1th position
					}
		k=a[f];
		for(i=f;i<n-1;i++)
			a[i]=a[i+1];
		a[n-1]=k;
	}
	else
	{
		for(i=0;i<n;i++)
			printf("%d ",a[i]);
		printf("\n");
	}
}

int main()
{
	int i,n,a[100];
	printf("\n Please input the number ");
	scanf("%d",&n);
	for(i=0;i<n;i++)			
		a[i]=i;        //Array initialized to numbers from 0 to n-1
	permute(a,0,n);
	return 0;
}