从字法上最小长度N的排列，使得对于正好为K个索引，a[i] a[i]+1

本文概述

• C ++
• Java
• Python3
• C#
• 的PHP

给定两个整数N和K, 任务是生成N个数字的排列(从1到N的每个数字恰好发生一次), 使得a [i]> a [i + 1]的索引数恰好为K。如果无法进行此类排列, 则打印"不可能"。

例子：

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

方法：由于排列应在字典上最小, 同时满足k个索引的条件, 即a [i]> a [i + 1]。因此, 对于此开始, K + 1个数字应按降序排列, 其余的应按升序排列。因此, 只需将K数字从N打印到1。然后将数字从1打印到N-K。

例如：N = 6, K = 4从N到1打印K个数字, 即6、5、4、3从1到NK打印NK数字, 即1, 2置换将是654312, 即, 起始4个索引满足a [i]>对于i = 1到k的a [i + 1]。

下面是上述方法的实现：

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..
?>

输出如下：

5 4 3 1 2

时间复杂度：O(N)

---