Permutación lexicográficamente más pequeña de los primeros N números naturales que tienen K índices perfectos

Dados dos enteros positivos N y K , la tarea es encontrar lexicográficamente la permutación más pequeña de los primeros N números naturales tal que haya exactamente K índices perfectos.
 

Se dice que un índice i en una array es perfecto si todos los elementos en los índices más pequeños que i son más pequeños que el elemento en el índice i .
 

Ejemplos:

Entrada: N = 10, K = 3
Salida: 8 9 10 1 2 3 4 5 6 7
Explicación: Hay exactamente 3 índices perfectos 0, 1 y 2.

Entrada: N = 12, K = 4
Salida: 9 10 11 12 1 2 3 4 5 6 7 8

Enfoque ingenuo: la idea es generar todas las permutaciones posibles de los primeros N números naturales e imprimir esa permutación que es lexicográficamente más pequeña y tiene K índices perfectos . 
Complejidad temporal: O(N*N!) 
Espacio auxiliar: O(1)
 

Enfoque eficiente: para optimizar el enfoque anterior, la idea es observar que la permutación más pequeña tendrá los últimos K elementos del rango [1, N] al frente en orden creciente. Los elementos restantes se pueden agregar en orden creciente. Siga los pasos a continuación para resolver el problema:

• Inicialice una array A[] para almacenar la permutación lexicográficamente más pequeña de los primeros N números naturales.
• Itere sobre el rango [0, K – 1] usando una variable, digamos i , y actualice el elemento de array A[i] para almacenar (N – K + 1) + i .
• Itere sobre el rango [K, N – 1] usando la variable i y actualice el elemento de array A[i] a (i – K + 1) .
• Después de completar los pasos anteriores, imprima la array A[] que contiene lexicográficamente la permutación más pequeña con K índices perfectos .
   

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

// C++ program for the above approach
#include <iostream>
using namespace std;
 
// Function to print the lexicographically
// smallest permutation with K perfect indices
void findPerfectIndex(int N, int K)
{
    // Iterator to traverse the array
    int i = 0;
 
    // Traverse first K array indices
    for (; i < K; i++) {
        cout << (N - K + 1) + i << " ";
    }
 
    // Traverse remaining indices
    for (; i < N; i++) {
        cout << i - K + 1 << " ";
    }
}
 
// Driver Code
int main()
{
    int N = 10, K = 3;
    findPerfectIndex(N, K);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG
{
 
// Function to print the lexicographically
// smallest permutation with K perfect indices
static void findPerfectIndex(int N, int K)
{
   
    // Iterator to traverse the array
    int i = 0;
 
    // Traverse first K array indices
    for (; i < K; i++)
    {
        System.out.print((N - K + 1) + i+ " ");
    }
 
    // Traverse remaining indices
    for (; i < N; i++)
    {
        System.out.print(i - K + 1+ " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 10, K = 3;
    findPerfectIndex(N, K);
}
}
 
// This code is contributed by shikhasingrajput

# Python program for the above approach
 
# Function to print the lexicographically
# smallest permutation with K perfect indices
def findPerfectIndex(N, K) :
     
    # Iterator to traverse the array
    i = 0
 
    # Traverse first K array indices
    for i in range(K):
        print((N - K + 1) + i, end = " ")
     
 
    # Traverse remaining indices
    for i in range(3, N):
        print( i - K + 1, end = " ")
     
# Driver Code
 
N = 10
K = 3
findPerfectIndex(N, K)
 
# This code is contributed by code_hunt.

// C# program for the above approach
using System;
class GFG
{
 
// Function to print the lexicographically
// smallest permutation with K perfect indices
static void findPerfectIndex(int N, int K)
{
   
    // Iterator to traverse the array
    int i = 0;
 
    // Traverse first K array indices
    for (; i < K; i++)
    {
        Console.Write((N - K + 1) + i+ " ");
    }
 
    // Traverse remaining indices
    for (; i < N; i++)
    {
        Console.Write(i - K + 1+ " ");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 10, K = 3;
    findPerfectIndex(N, K);
}
}
 
// This code is contributed by susmitakundugoaldanga.

<script>
 
// javascript program for the above approach
// Function to print the lexicographically
// smallest permutation with K perfect indices
function findPerfectIndex(N , K)
{
   
    // Iterator to traverse the array
    var i = 0;
 
    // Traverse first K array indices
    for (; i < K; i++)
    {
        document.write((N - K + 1) + i+ " ");
    }
 
    // Traverse remaining indices
    for (; i < N; i++)
    {
        document.write(i - K + 1+ " ");
    }
}
 
// Driver Code
var N = 10, K = 3;
findPerfectIndex(N, K);
 
// This code is contributed by 29AjayKumar
</script>

8 9 10 1 2 3 4 5 6 7

Complejidad temporal: O(N)
Espacio auxiliar: O(1)