Dados dos enteros N y K , la tarea es encontrar una permutación de los primeros N números naturales con exactamente K inversiones .
Ejemplos:
Entrada: N = 5, K = 4
Salida: 5 1 2 3 4
Explicación: En la permutación P anterior, los pares (i, j) tales que i < j y P[i] > P[j] son (0, 1), (0, 2), (0, 3) y (0, 4). Por lo tanto, el número de inversiones en la permutación anterior es 4, que es el valor requerido.Entrada: N = 3, K = 4
Salida: -1
Explicación: Ninguna permutación posible de los primeros 3 números naturales tiene exactamente 4 inversiones.
Enfoque: el problema dado se puede resolver mediante un enfoque codicioso . Se puede observar que si el elemento máximo de un arreglo de N elementos se asigna en la i -ésima posición, contribuirá con (N – i) inversiones . Usando esta observación, siga los pasos a continuación para resolver el problema dado:
- Compruebe la condición de si K > el número máximo de inversiones posibles (es decir, N*(N-1)/2). Si es verdadero, devuelve -1 .
- Cree una variable curr , que realiza un seguimiento del elemento máximo actual de la array. Inicialmente curr = N .
- Cree una array p[] , que realiza un seguimiento de la permutación actual.
- Itere usando una variable i en el rango [1, N] , y si K > (curr – i) , asigne curr a la posición actual de la array y reste (curr – i ) de K. Además, disminuya el valor de curr en 1.
- Si K > (curr – i) es falso, asigne K+1 al índice actual y asigne los enteros restantes en orden creciente en la array p[] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to fint the permutation of
// N natural numbers with k inversions
void findPermutation(int n, int k)
{
// Stores the maximum number of inversions
int max_inv = (n * (n - 1)) / 2;
// If required inversions are more that max
if (k > max_inv) {
cout << "-1";
return;
}
// Stores the final permutation
int p[n + 1];
// Keep track of the current max element
// in the permutation
int curr = n;
int i = 1;
// Loop to iterate through the array
for (i = 1; i <= n; i++) {
// Set current element as ith element
// in order to increase n-i inversions
// in the given permutation
if (k >= n - i) {
p[i] = curr;
curr--;
k -= (n - i);
}
// Otherwise set (k+1) element at ith index
// ans assign the remaining indices
else {
// If the remaining inversion count is
// greater than 0
if (k == 0) {
i--;
}
else {
p[i] = k + 1;
}
// Set the next index as 1
p[i + 1] = 1;
// Loop to assign the remaining indices
for (int j = i + 2; j <= n; j++) {
p[j] = p[j - 1] + 1;
// If current element already occurred
if (p[i] == p[j]) {
p[j]++;
}
}
break;
}
}
// Print Answer
for (int j = 1; j <= n; j++) {
cout << p[j] << " ";
}
}
// Driver code
int main()
{
int n = 5;
int k = 4;
findPermutation(n, k);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to fint the permutation of
// N natural numbers with k inversions
static void findPermutation(int n, int k)
{
// Stores the maximum number of inversions
int max_inv = (n * (n - 1)) / 2;
// If required inversions are more that max
if (k > max_inv) {
System.out.println("-1");
return;
}
// Stores the final permutation
int [] p = new int[n+1];
// Keep track of the current max element
// in the permutation
int curr = n;
int i = 1;
// Loop to iterate through the array
for (i = 1; i <= n; i++) {
// Set current element as ith element
// in order to increase n-i inversions
// in the given permutation
if (k >= n - i) {
p[i] = curr;
curr--;
k -= (n - i);
}
// Otherwise set (k+1) element at ith index
// ans assign the remaining indices
else {
// If the remaining inversion count is
// greater than 0
if (k == 0) {
i--;
}
else {
p[i] = k + 1;
}
// Set the next index as 1
p[i + 1] = 1;
// Loop to assign the remaining indices
for (int j = i + 2; j <= n; j++) {
p[j] = p[j - 1] + 1;
// If current element already occurred
if (p[i] == p[j]) {
p[j]++;
}
}
break;
}
}
// Print Answer
for (int j = 1; j <= n; j++) {
System.out.print(p[j] + " ");
}
}
// Driver code
public static void main (String[] args) {
int n = 5;
int k = 4;
findPermutation(n, k);
}
}
// This code is contributed by Potta Lokesh
Python3
# python program of the above approach
# Function to fint the permutation of
# N natural numbers with k inversions
def findPermutation(n, k):
# Stores the maximum number of inversions
max_inv = (n * (n - 1)) / 2
# If required inversions are more that max
if (k > max_inv):
print("-1")
return
# Stores the final permutation
p = [0 for _ in range(n + 1)]
# Keep track of the current max element
# in the permutation
curr = n
i = 1
# Loop to iterate through the array
for i in range(1, n+1):
# Set current element as ith element
# in order to increase n-i inversions
# in the given permutation
if (k >= n - i):
p[i] = curr
curr -= 1
k -= (n - i)
# Otherwise set (k+1) element at ith index
# ans assign the remaining indices
else:
# If the remaining inversion count is
# greater than 0
if (k == 0):
i -= 1
else:
p[i] = k + 1
# Set the next index as 1
p[i + 1] = 1
# Loop to assign the remaining indices
for j in range(i+2, n+1):
p[j] = p[j - 1] + 1
# If current element already occurred
if (p[i] == p[j]):
p[j] += 1
break
# Print Answer
for j in range(1, n+1):
print(p[j], end=" ")
# Driver code
if __name__ == "__main__":
n = 5
k = 4
findPermutation(n, k)
# This code is contributed by rakeshsahni
Javascript
<script>
// JavaScript program of the above approach
// Function to fint the permutation of
// N natural numbers with k inversions
const findPermutation = (n, k) => {
// Stores the maximum number of inversions
let max_inv = (n * (n - 1)) / 2;
// If required inversions are more that max
if (k > max_inv) {
document.write("-1");
return;
}
// Stores the final permutation
let p = new Array(n + 1).fill(0);
// Keep track of the current max element
// in the permutation
let curr = n;
let i = 1;
// Loop to iterate through the array
for (i = 1; i <= n; i++) {
// Set current element as ith element
// in order to increase n-i inversions
// in the given permutation
if (k >= n - i) {
p[i] = curr;
curr--;
k -= (n - i);
}
// Otherwise set (k+1) element at ith index
// ans assign the remaining indices
else {
// If the remaining inversion count is
// greater than 0
if (k == 0) {
i--;
}
else {
p[i] = k + 1;
}
// Set the next index as 1
p[i + 1] = 1;
// Loop to assign the remaining indices
for (let j = i + 2; j <= n; j++) {
p[j] = p[j - 1] + 1;
// If current element already occurred
if (p[i] == p[j]) {
p[j]++;
}
}
break;
}
}
// Print Answer
for (let j = 1; j <= n; j++) {
document.write(`${p[j]} `);
}
}
// Driver code
let n = 5;
let k = 4;
findPermutation(n, k);
// This code is contributed by rakeshsahni
</script>
C#
// C# program for the above approach
using System;
public class GFG {
// Function to fint the permutation of
// N natural numbers with k inversions
static void findPermutation(int n, int k)
{
// Stores the maximum number of inversions
int max_inv = (n * (n - 1)) / 2;
// If required inversions are more that max
if (k > max_inv) {
Console.WriteLine("-1");
return;
}
// Stores the final permutation
int [] p = new int[n+1];
// Keep track of the current max element
// in the permutation
int curr = n;
int i = 1;
// Loop to iterate through the array
for (i = 1; i <= n; i++) {
// Set current element as ith element
// in order to increase n-i inversions
// in the given permutation
if (k >= n - i) {
p[i] = curr;
curr--;
k -= (n - i);
}
// Otherwise set (k+1) element at ith index
// ans assign the remaining indices
else {
// If the remaining inversion count is
// greater than 0
if (k == 0) {
i--;
}
else {
p[i] = k + 1;
}
// Set the next index as 1
p[i + 1] = 1;
// Loop to assign the remaining indices
for (int j = i + 2; j <= n; j++) {
p[j] = p[j - 1] + 1;
// If current element already occurred
if (p[i] == p[j]) {
p[j]++;
}
}
break;
}
}
// Print Answer
for (int j = 1; j <= n; j++) {
Console.Write(p[j] + " ");
}
}
// Driver code
public static void Main (string[] args) {
int n = 5;
int k = 4;
findPermutation(n, k);
}
}
// This code is contributed by AnkThon
Producción
5 1 2 3 4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por subhankarjadab y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA