Permutación lexicográficamente más pequeña de longitud N tal que para exactamente K índices, a[i] > a[i] + 1

Dados dos números enteros N y K, la tarea es generar una permutación de N números (Cada número de 1 a N ocurre exactamente una vez) tal que el número de índices donde a[i]>a[i+1] sea exactamente K. Escriba «No es posible» si no es posible tal permutación.
Ejemplos: 
 

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

Enfoque: Dado que la permutación debería ser lexicográficamente la más pequeña con la condición satisfecha para k índices, es decir, a[i] > a[i+1]. Entonces, para eso, los dígitos K + 1 iniciales deben estar en orden decreciente y los restantes deben estar en orden creciente. Así que simplemente imprima los números K de N a 1. Luego imprima los números de 1 a NK. 
 

Por ejemplo: N = 6, K = 4 
Imprime números K de N a 1, es decir, 6, 5, 4, 3 
Imprime números NK de 1 a NK, es decir, 1, 2
La permutación será 654312, es decir, 4 índices iniciales satisfacen a[i] > a[i+1] para i = 1 a k. 
 

A continuación se muestra la implementación del enfoque anterior: 
 

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

<script>
// javascript implementation of the above approach
function printPermutation(n , k)
{
    var i, mx = n;
    for (i = 1; i <= k; i++) // Decreasing part
    {
        document.write( mx + " ");
        mx--;
    }
    for (i = 1; i <= mx; i++) // Increasing part
        document.write( i + " ");
}
 
// Driver Code
var N = 5, K = 3;
 
if (K >= N - 1)
    document.write( "Not Possible");
 
else
    printPermutation(N, K);
 
// This code is contributed by 29AjayKumar
</script>

5 4 3 1 2

Complejidad de tiempo: O(N)