/* 
As an exercise, comment the program yourself
*/

#include<stdio.h>
#include<math.h>
#include<stdlib.h>

void PrintPermutation(int *matrix, int n)
{
   int i;  
   for(i=0;i<n;i++)
      printf("%d \t",matrix[i]);

   printf("\n");
   return;
}

void swap(int *matrix, int x, int y)
{
  int temp; 
  temp = matrix[x]; 
  matrix[x] = matrix[y]; 
  matrix[y] = temp; 
  return; 
}

void Permute(int *matrix, int k,int n, int *number_per)
{
  int i;
  if(k==n) { 
  	PrintPermutation(matrix,n); (*number_per)++;}
  else {
  	for(i=k;i<n;i++){
  	      swap(matrix,i,k);
              Permute(matrix,k+1,n,number_per);
	      swap(matrix,k,i);
        }
  }
  return;
}


int* allocate1D(int row){
  int *S;
  S=(int *)calloc(row,sizeof(int));
  if(S==NULL){
	printf("\n No space \n"); exit(0);
  }
 
 return S;
}

 int main(void){
 int i, m, *matrix, number_per=0; 
 printf("\n How many numbers you want to permute::>"); 
 scanf("%d",&m);
 
 matrix = allocate1D(m);
 /*Fill the matrix with numbers from 1 to m */
 for(i=0;i<m;i++)
   matrix[i] = i+1; 

 Permute(matrix,0,m,&number_per);
 printf("\n Total number of permutations::> %d",number_per); 

 printf("\n");
 return 0;
}