Encuentre la permutación de N números en el rango [1, N] de modo que los K números tengan el mismo valor que su índice

Dado un entero positivo N y un entero K tal que 0 ≤ K ≤ N , la tarea es encontrar cualquier permutación A de [1, N] tal que el número de índices para los que A _i = i sea exactamente K ( basado en 1 indexación ). Si no existe tal permutación, imprima −1 .

Ejemplos:

Entrada: N = 3, K = 1
Salida: 1 3 2
Explicación: Considere la permutación A = [1, 3, 2]. Tenemos A1=1, A2=3 y A3=2. 
Entonces, esta permutación tiene exactamente 1 índice tal que A _i = i.

Entrada: N = 2, K = 1
Salida: -1
Explicación: hay un total de 2 permutaciones de [1, 2] que son [1, 2] y [2, 1]. 
Hay 2 índices en [1, 2] y 0 índices en [2, 1] para los cuales A _i = i se cumple. 
Por lo tanto, no existe ninguna permutación de [1, 2] con exactamente 1 índice i para el cual Ai=i se cumple.

Enfoque: la tarea se puede resolver utilizando el enfoque codicioso . Inicialmente fije exactamente K elementos en sus índices y luego simplemente coloque aleatoriamente elementos NK en diferentes lugares. Siga los pasos a continuación para resolver el problema:

1. De alguna manera arregla las posiciones K
2. Dislocar los números NK restantes
3. Desplazamiento cíclico del elemento restante en uno

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print permutation
void permutation(int N, int K)
{
    if (K == N) {
        for (int i = 1; i <= N; i++) {
            cout << i << ' ';
        }
        cout << '\n';
    }
    else if (K == N - 1) {
        cout << "-1" << '\n';
    }
    else {
        for (int i = 1; i <= K; i++) {
            cout << i << ' ';
        }
        for (int i = K + 2; i <= N; i++) {
            cout << i << ' ';
        }
        cout << K + 1 << '\n';
    }
}
 
// Driver Code
int main()
{
    int N = 3;
    int K = 1;
    permutation(N, K);
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
public class GFG
{
 
// Function to print permutation
static void permutation(int N, int K)
{
    if (K == N) {
        for (int i = 1; i <= N; i++) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
    else if (K == N - 1) {
        System.out.println("-1");
    }
    else {
        for (int i = 1; i <= K; i++) {
            System.out.print(i + " ");
        }
        for (int i = K + 2; i <= N; i++) {
            System.out.print(i + " ");
        }
        System.out.println(K + 1);
    }
}
 
// Driver Code
public static void main(String args[])
{
    int N = 3;
    int K = 1;
    permutation(N, K);
}
}
 
// This code is contributed by Samim Hossain Mondal.

# Python code for the above approach
 
# Function to print permutation
def permutation(N, K):
    if (K == N):
        for i in range(1, N + 1):
            print(i, end=" ")
        print('')
    elif (K == N - 1):
        print(-1)
    else:
        for i in range(1, K + 1):
            print(i, end=" ")
        for i in range(K + 2, N + 1):
            print(i, end=" ")
        print(K + 1)
 
# Driver Code
N = 3;
K = 1;
permutation(N, K);
 
# This code is contributed by Saurabh Jaiswal

// C# program to implement
// the above approach
using System;
public class GFG {
 
  // Function to print permutation
  static void permutation(int N, int K)
  {
    if (K == N) {
      for (int i = 1; i <= N; i++) {
        Console.Write(i + " ");
      }
      Console.WriteLine();
    }
    else if (K == N - 1) {
      Console.WriteLine("-1");
    }
    else {
      for (int i = 1; i <= K; i++) {
        Console.Write(i + " ");
      }
      for (int i = K + 2; i <= N; i++) {
        Console.Write(i + " ");
      }
      Console.Write(K + 1);
    }
  }
 
  // Driver Code
  public static void Main()
  {
    int N = 3;
    int K = 1;
    permutation(N, K);
  }
}
 
// This code is contributed by ukasp.

<script>
      // JavaScript code for the above approach
 
      // Function to print permutation
      function permutation(N, K) {
          if (K == N) {
              for (let i = 1; i <= N; i++) {
                  document.write(i + " ")
              }
              document.write('<br>')
          }
          else if (K == N - 1) {
              document.write(-1 + '<br>')
          }
          else {
              for (let i = 1; i <= K; i++) {
                  document.write(i + " ")
              }
              for (let i = K + 2; i <= N; i++) {
                  document.write(i + " ")
              }
              document.write(K + 1 + '<br>')
          }
      }
 
      // Driver Code
      let N = 3;
      let K = 1;
      permutation(N, K);
 
// This code is contributed by Potta Lokesh
  </script>

1 3 2

Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)