Lexicographically Preceding Permutation(C Program)

   Lexicographically Preceding Permutation                                  (C Program)

Given an integer n and a permutation of numbers 1, 2 ... , n-1, n write a program to print the permutation that lexicographically precedes the given input permutation. If the given permutation is the lexicographically least permutation, then print the input permutation itself. 

Input Format: 
First line is the value of integer n: 1 <= n <= 1,000,000
Second line is a space separated list of integers 1 2 ... n permuted in some random order

Output Format:

Output a single line containing a space separated list of integers which is the lexicographically preceding permutation of the input permutation.

Example:-

3

Possible 6 permutations in order are:-

123

132

213

231

312

321

1.  Input:-      132

    Output:-    123

2.  Input:-      321

    Output:-    312

3.  Input:-      231

    Output:-    213

4.  Input:-      312

    Output:-    231

5.  Input:-      213

    Output:-    132

Algorithm:-

1.Sort the input compare with minimum,if equals input is preceding order. 

2.Perform -1 with input.

3.Sort it in Ascending order.

4.Compare it with sorted input.

5.If equals calculated is preceding string,otherwise go to step 2.

Program:-

#include<stdio.h>

int check(int a[],int b[],int n){
 int flag=1;
 for(int i=0;i<n;i++){
  if(a[i]!=b[i]){
   flag=0;
   break;
  }
 }
 return flag;
}
void sort(int a[],int n){
 int temp;
 for(int i=0;i<n;i++){
  for(int j=i;j<n;j++){
   if(a[i]>a[j]){
    temp=a[i];
    a[i]=a[j];
    a[j]=temp;
   }
  }
 }
}
void minus(int a[],int n){
 for(int i=n-1;i>=0;i--){
  if(a[i]!=0){
   a[i]=a[i]-1;
   break;
  }else{
   a[i]=9;
   if(a[i-1]==0){
    minus(a,n-1);
    break;
   }else{
    a[i-1]=a[i-1]-1;
    break;
   }
  }
 }
}

int main(){
 int n;
 scanf("%d",&n);
 int a[n],min[n],b[n];
 for(int i=0;i<n;i++){
  scanf("%d",&a[i]);
  min[i]=i+1;
  b[i]=a[i];
 }
 int temp,done=0;
 while(1){
  if(check(a,min,n)){
   break;
  }else{
   for(int i=0;i<n;i++){
    a[i]=b[i];
   }
   minus(a,n);
   minus(b,n);
   sort(a,n);
  }
 }
 printf("%d",b[0]);
 for(int i=1;i<n;i++){
  printf(" %d",b[i]);
 }
 return 0;
}

---------------X---------------X---------------X---------------X---------------

1.Input:-

  4
  3 1 2 4
  Output:-

  2 4 3 1
2.Input:-
  7
  1 2 3 4 5 6 7
  Output:-

  1 2 3 4 5 6 7
3.Input:-
  12
  3 1 2 4 5 6 7 8 9 10 11 12
  Output:-

  2 12 11 10 9 8 7 6 5 4 3 1