Typically, the minimum length N is arranged such that for exactly K indexes, a[i] a[i]+1

Given two integers N and K, the task is to generate an arrangement of N numbers (each number from 1 to N happens exactly once) such that the number of indexes for a [i]> a [i + 1] is exactly K. If such an arrangement is not possible, it is not possible to print.

Example:

Input: N = 5, K = 3
Output: 5 4 3 1 2
Starting 3 indices satisfying the condition 
a[i]> a[i]+1

Input: N = 7, k = 4
Output: 7 6 5 4 1 2 3

Method: Since the arrangement should be the smallest in the dictionary, the condition of k indexes should be satisfied, i.e., a [i]> a [i + 1]. Therefore, for this start, the K+1 digits should be in descending order and the rest in ascending order. So, just print the K number from N to 1. Then print the numbers from 1 to N-K.

For example: N = 6, K = 4 print K digits from N to 1, i.e. 6, 5, 4, 3 print NK digits from 1 to NK, i.e. 1, 2 permutations will be 654312, i.e., the first 4 indexes satisfy a[i]> for i = 1 to k a[i + 1].

Here’s an implementation of the above method:

C ++

//C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
  
void printPermutation( int n, int k)
{
     int i, mx = n;
     for (i = 1; i <= k; i++) //Decreasing part
     {
         cout <<mx <<" " ;
         mx--;
     }
     for (i = 1; i <= mx; i++) //Increasing part
         cout <<i <<" " ;
}
  
//Driver Code
int main()
{
     int N = 5, K = 3;
  
     if (K>= N - 1)
         cout <<"Not Possible" ;
  
     else
         printPermutation(N, K);
  
     return 0;
}

Java

//Java implementation of the above approach
  
import java.io.*;
  
class GFG {
  
  
static void printPermutation( int n, int k)
{
     int i, mx = n;
     for (i = 1 ; i <= k; i++) //Decreasing part
     {
         System.out.print( mx + " " );
         mx--;
     }
     for (i = 1 ; i <= mx; i++) //Increasing part
         System.out.print( i + " " );
}
  
//Driver Code
  
     public static void main (String[] args) {
             int N = 5 , K = 3 ;
  
     if (K>= N - 1 )
         System.out.print( "Not Possible" );
  
     else
         printPermutation(N, K);
     }
}
  
//This code is contributed by inder_verma..

Python3

# Python3 implementation of the
# above approach 
def printPermutation(n, k): 
  
     mx = n 
     for i in range ( 1 , k + 1 ): # Decreasing part 
         print (mx, end = " " ) 
         mx - = 1
      
     for i in range ( 1 , mx + 1 ): # Increasing part 
         print (i, end = " " ) 
  
# Driver Code 
if __name__ = = "__main__" :
  
     N, K = 5 , 3
  
     if K> = N - 1 : 
         print ( "Not Possible" ) 
  
     else :
         printPermutation(N, K) 
  
# This code is contributed
# by Rituraj Jain

C#

//C# implementation of the above approach
using System;
class GFG {
  
  
static void printPermutation( int n, int k)
{
     int i, mx = n;
     for (i = 1; i <= k; i++) //Decreasing part
     {
         Console.Write( mx + " " );
         mx--;
     }
     for (i = 1; i <= mx; i++) //Increasing part
         Console.Write( i + " " );
}
  
//Driver Code
  
     public static void Main () {
             int N = 5, K = 3;
  
     if (K>= N - 1)
         Console.WriteLine( "Not Possible" );
  
     else
         printPermutation(N, K);
     }
}
  
//This code is contributed by inder_verma..

PHP

<?php
//PHP  implementation of the above approach
  
function printPermutation( $n , $k )
{
     $i ; $mx = $n ;
     for ( $i = 1; $i <= $k ; $i ++) //Decreasing part
     {
         echo  $mx , " " ;
         $mx --;
     }
     for ( $i = 1; $i <= $mx ; $i ++) //Increasing part
         echo $i , " " ;
}
  
//Driver Code
  
     $N = 5; $K = 3;
  
     if ( $K>= $N - 1)
         echo "Not Possible" ;
  
     else
         printPermutation( $N , $K );
  
  
//This code is contributed by inder_verma..
?>

The output is as follows:

5 4 3 1 2

Time Complexity: O(N)