Dados dos números enteros N y K , la tarea es contar el número de permutaciones de los primeros N números naturales que tienen exactamente K inversiones. Dado que el conteo puede ser muy grande, imprímalo módulo 10 9 + 7 .
Una inversión se define como un par a[i], a[j] tal que a[i] > a[j] e i < j .
Ejemplos:
Entrada: N = 3, K = 2
Salida: 2
Explicación:
Todas las permutaciones para N = 3 son 321, 231, 213, 312, 132, 123.
De las cuales solo 231 y 312 tienen 2 inversiones como:
- 231: 2 > 1 y 3 > 1
- 312: 3 > 1 y 3 > 2.
Por lo tanto, ambos cumplen la condición de tener exactamente K inversiones.
Entrada: N = 5, K = 5
Salida: 22
Enfoque ingenuo: consulte la publicación anterior para conocer el enfoque más simple posible para resolver el problema.
Complejidad temporal: O(N*N!)
Espacio auxiliar: O(1)
Programación dinámica utilizando el enfoque de arriba hacia abajo: consulte la publicación anterior de este artículo para el enfoque de arriba hacia abajo.
Complejidad de Tiempo: O(N*K 2 )
Espacio Auxiliar: O(N*K)
Programación dinámica utilizando el enfoque ascendente:
Ilustración:
Por ejemplo: N = 4, K = 2
N – 1 = 3, K 0 = 0 … 123 => 1423
N – 1 = 3, K 1 = 1 … 213, 132 => 2143, 1342
N – 1 = 3, K 2 = 2 … 231, 312 => 2314, 3124
Entonces la respuesta es 5 .El valor máximo se toma entre (K – N + 1) y 0 ya que no se pueden obtener K inversiones si el número de inversiones en permutación de (N – 1) números es menor que K – (N – 1) como máximo (N – 1) Se pueden obtener nuevas inversiones sumando el número N al principio.
Siga los pasos a continuación para resolver el problema:
- Cree una array auxiliar dp[2][K + 1] donde dp[N][K] almacena todas las permutaciones de (N – 1) números con K = (max(K – (N – 1), 0) a K) inversiones, sumando N número con ellos una sola vez.
- El uso de dp[i % 2][K] intercambiará la iteración entre dos filas y tomará j = Max(K – (N – 1), 0) . Entonces dp[N[K] = dp[N-1][j] + dp[N-1][j+1] + …. + dp[N – 1][K] .
- Para calcular dp[N][K] no es necesario realizar esta iteración adicional de K , ya que se puede obtener en O(1) a partir de dp[N][K – 1] . Entonces la relación de recurrencia viene dada por:
- dp[N][K] = dp[N][K – 1] + dp[N – 1][K] – dp[N – 1][máx(K – (N – 1), 0) – 1]
- Itere dos bucles anidados usando la variable i y j sobre N y K respectivamente y actualice cada estado de dp según la relación de recurrencia anterior.
- Imprima el valor de dp[N%2][K] después de los pasos anteriores como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count permutations with
// K inversions
int numberOfPermWithKInversion(
int N, int K)
{
// Store number of permutations
// with K inversions
int dp[2][K + 1];
int mod = 1000000007;
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= K; j++) {
// If N = 1 only 1 permutation
// with no inversion
if (i == 1)
dp[i % 2][j] = (j == 0);
// For K = 0 only 1 permutation
// with no inversion
else if (j == 0)
dp[i % 2][j] = 1;
// Otherwise Update each dp
// state as per the reccurrance
// relation formed
else
dp[i % 2][j]
= (dp[i % 2][j - 1] % mod
+ (dp[1 - i % 2][j]
- ((max(j - (i - 1), 0) == 0)
? 0
: dp[1 - i % 2]
[max(j - (i - 1), 0)
- 1])
+ mod)
% mod)
% mod;
;
}
}
// Print final count
cout << dp[N % 2][K];
}
// Driver Code
int main()
{
// Given N and K
int N = 3, K = 2;
// Function Call
numberOfPermWithKInversion(N, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to count permutations with
// K inversions
static void numberOfPermWithKInversion(int N, int K)
{
// Store number of permutations
// with K inversions
int[][] dp = new int[2][K + 1];
int mod = 1000000007;
for(int i = 1; i <= N; i++)
{
for(int j = 0; j <= K; j++)
{
// If N = 1 only 1 permutation
// with no inversion
if (i == 1)
{
dp[i % 2][j] = (j == 0) ? 1 : 0;
}
// For K = 0 only 1 permutation
// with no inversion
else if (j == 0)
dp[i % 2][j] = 1;
// Otherwise Update each dp
// state as per the reccurrance
// relation formed
else
{
int maxm = Math.max(j - (i - 1));
dp[i % 2][j] = (dp[i % 2][j - 1] % mod +
(dp[1 - i % 2][j] -
((Math.max(j - (i - 1), 0) == 0) ?
0 : dp[1 - i % 2][maxm, 0) - 1]) +
mod) % mod) % mod;
}
}
}
// Print final count
System.out.println (dp[N % 2][K]);
}
// Driver Code
public static void main(String[] args)
{
// Given N and K
int N = 3, K = 2;
// Function Call
numberOfPermWithKInversion(N, K);
}
}
// This code is contributed by akhilsaini
Python3
# Python3 program for the above approach # Function to count permutations with # K inversions def numberOfPermWithKInversion(N, K): # Store number of permutations # with K inversions dp = [[0] * (K + 1)] * 2 mod = 1000000007 for i in range(1, N + 1): for j in range(0, K + 1): # If N = 1 only 1 permutation # with no inversion if (i == 1): dp[i % 2][j] = 1 if (j == 0) else 0 # For K = 0 only 1 permutation # with no inversion elif (j == 0): dp[i % 2][j] = 1 # Otherwise Update each dp # state as per the reccurrance # relation formed else: var = (0 if (max(j - (i - 1), 0) == 0) else dp[1 - i % 2][max(j - (i - 1), 0) - 1]) dp[i % 2][j] = ((dp[i % 2][j - 1] % mod + (dp[1 - i % 2][j] - (var) + mod) % mod) % mod) # Print final count print(dp[N % 2][K]) # Driver Code if __name__ == '__main__': # Given N and K N = 3 K = 2 # Function Call numberOfPermWithKInversion(N, K) # This code is contributed by akhilsaini
C#
// C# program for the above approach
using System;
class GFG{
// Function to count permutations with
// K inversions
static void numberOfPermWithKInversion(int N, int K)
{
// Store number of permutations
// with K inversions
int[,] dp = new int[2, K + 1];
int mod = 1000000007;
for(int i = 1; i <= N; i++)
{
for(int j = 0; j <= K; j++)
{
// If N = 1 only 1 permutation
// with no inversion
if (i == 1)
{
dp[i % 2, j] = (j == 0) ? 1 : 0;
}
// For K = 0 only 1 permutation
// with no inversion
else if (j == 0)
dp[i % 2, j] = 1;
// Otherwise Update each dp
// state as per the reccurrance
// relation formed
else
dp[i % 2, j] = (dp[i % 2, j - 1] % mod +
(dp[1 - i % 2, j] -
((Math.Max(j - (i - 1), 0) == 0) ?
0 : dp[1 - i % 2, Math.Max(
j - (i - 1), 0) - 1]) +
mod) % mod) % mod;
}
}
// Print final count
Console.WriteLine(dp[N % 2, K]);
}
// Driver Code
public static void Main()
{
// Given N and K
int N = 3, K = 2;
// Function Call
numberOfPermWithKInversion(N, K);
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to count permutations with
// K inversions
function numberOfPermWithKInversion(N, K)
{
// Store number of permutations
// with K inversions
let dp = new Array(2);
// Loop to create 2D array using 1D array
for (var i = 0; i < dp.length; i++)
{
dp[i] = new Array(2);
}
let mod = 1000000007;
for(let i = 1; i <= N; i++)
{
for(let j = 0; j <= K; j++)
{
// If N = 1 only 1 permutation
// with no inversion
if (i == 1)
{
dp[i % 2][j] = (j == 0) ? 1 : 0;
}
// For K = 0 only 1 permutation
// with no inversion
else if (j == 0)
dp[i % 2][j] = 1;
// Otherwise Update each dp
// state as per the reccurrance
// relation formed
else
dp[i % 2][j] = (dp[i % 2][j - 1] % mod +
(dp[1 - i % 2][j] -
((Math.max(j - (i - 1), 0) == 0) ?
0 : dp[1 - i % 2][Math.max(j -
(i - 1), 0) - 1]) +
mod) % mod) % mod;
}
}
// Print final count
document.write(dp[N % 2][K]);
}
// Driver Code
// Given N and K
let N = 3, K = 2;
// Function Call
numberOfPermWithKInversion(N, K);
</script>
2
Complejidad temporal: O(N * K)
Espacio auxiliar: O(K)