Número de permutaciones con K inversiones

Posted on by Rudeus Greyrat

Dada una array, una inversión se define como un par a[i], a[j] tal que a[i] > a[j] e i < j. Nos dan dos números N y k, necesitamos decir cuántas permutaciones del primer número N tienen exactamente la inversión K.

Ejemplos: 

Input  : N = 3, K = 1
Output : 2
Explanation :  
Total Permutation of first N number,
123, 132, 213, 231, 312, 321
Permutation with 1 inversion : 132 and 213

Input  : N = 4, K = 2
Output : 5

Una forma ingenua de resolver este problema es anotar todas las permutaciones y luego verificar el recuento de inversión en ellas, pero iterar a través de la permutación en sí tomará O (N!) Tiempo, que es demasiado grande. 

Podemos resolver este problema utilizando un enfoque de programación dinámica. A continuación se muestra la fórmula recursiva.  

If N is 0, Count(0, K) = 0

If K is 0, Count(N, 0) = 1 (Only sorted array)

In general case, 
If we have N number and require K inversion, 
Count(N, K) = Count(N - 1, K) + 
              Count(N – 1, K - 1) + 
              Count(N – 1, K – 2) + 
              .... + 
              Count(N – 1, 0)

¿Cómo funciona la fórmula recursiva anterior?  
Si tenemos un número N y queremos tener una permutación K y suponemos que todas las permutaciones del número (N – 1) están escritas en alguna parte, el nuevo número (el número N y el más grande) debe colocarse en todas las permutaciones del número (N – 1) y aquellos cuya cuenta de inversión se convierte en K después de sumar este número deben agregarse en nuestra respuesta. Ahora tome esos conjuntos de permutación de (N – 1) número que ha dejado (K – 3) inversión, ahora podemos colocar este nuevo número más grande en la posición 3 desde el último, luego el conteo de inversión será K, entonces cuente (N – 1) , K – 3) se debe agregar a nuestra respuesta, el mismo argumento se puede dar también para otra inversión y llegaremos a la recursividad anterior como la respuesta final.

El siguiente código está escrito siguiendo la recursividad anterior en forma de memorización.  

C++

// C++ program to find number of permutation
// with K inversion using Memoization
#include <bits/stdc++.h>
using namespace std;
 
// Limit on N and K
const int M = 100;
 
// 2D array memo for stopping
// solving same problem again
int memo[M][M];
 
// method recursively calculates
// permutation with K inversion
int numberOfPermWithKInversion(int N, int K)
{
     
    // base cases
    if (N == 0)
        return 0;
    if (K == 0)
        return 1;
 
    // if already solved then
    // return result directly
    if (memo[N][K] != 0)
        return memo[N][K];
 
    // calling recursively all subproblem
    // of permutation size N - 1
    int sum = 0;
    for (int i = 0; i <= K; i++)
    {
 
        // Call recursively only
        // if total inversion
        // to be made are less
        // than size
        if (i <= N - 1)
            sum += numberOfPermWithKInversion(N - 1,
                                              K - i);
    }
 
    // store result into memo
    memo[N][K] = sum;
 
    return sum;
}
 
// Driver code
int main()
{
    int N = 4;
    int K = 2;
    cout << numberOfPermWithKInversion(N, K);
    return 0;
}

Java

// Java program to find number of permutation with
// K inversion using Memoization
 
import java.io.*;
 
class GFG {
     
    // Limit on N and K
    static int M = 100;
 
    // 2D array memo for stopping solving same problem
    // again
    static int memo[][] = new int[M][M];
 
    // method recursively calculates permutation with
    // K inversion
    static int numberOfPermWithKInversion(int N, int K)
    {
         
        // base cases
        if (N == 0)
            return 0;
        if (K == 0)
            return 1;
 
        // if already solved then return result directly
        if (memo[N][K] != 0)
            return memo[N][K];
 
        // calling recursively all subproblem of
        // permutation size N - 1
        int sum = 0;
        for (int i = 0; i <= K; i++) {
             
            // Call recursively only if total inversion
            // to be made are less than size
            if (i <= N - 1)
                sum += numberOfPermWithKInversion(N - 1,
                                                  K - i);
        }
 
        // store result into memo
        memo[N][K] = sum;
 
        return sum;
    }
 
    // Driver code to test above methods
    public static void main(String[] args)
    {
        int N = 4;
        int K = 2;
        System.out.println(numberOfPermWithKInversion(N, K));
    }
}
 
// This code is contributed by vt_m.

Python3

# Python3 program to find number of permutation
# with K inversion using Memoization
 
# Limit on N and K
M = 100
 
# 2D array memo for stopping 
# solving same problem again
memo = [[0 for i in range(M)] for j in range(M)]
  
# method recursively calculates
# permutation with K inversion
def numberOfPermWithKInversion(N, K):
 
    # Base cases
    if (N == 0): return 0
    if (K == 0): return 1
 
    # If already solved then
    # return result directly
    if (memo[N][K] != 0):
        return memo[N][K]
 
    # Calling recursively all subproblem
    # of permutation size N - 1
    sum = 0
    for i in range(K + 1):
     
        # Call recursively only if
        # total inversion to be made
        # are less than size
        if (i <= N - 1):
            sum += numberOfPermWithKInversion(N - 1, K - i)
     
    # store result into memo
    memo[N][K] = sum
 
    return sum
 
# Driver code
N = 4; K = 2
print(numberOfPermWithKInversion(N, K))
 
# This code is contributed by Anant Agarwal.

C#

// C# program to find number of
// permutation with K inversion
// using Memoization
using System;
 
class GFG
{
 
// Limit on N and K
static int M = 100;
 
// 2D array memo for stopping
// solving same problem again
static int [,]memo = new int[M, M];
 
// method recursively calculates
// permutation with K inversion
static int numberOfPermWithKInversion(int N,
                                      int K)
{
     
    // base cases
    if (N == 0)
        return 0;
    if (K == 0)
        return 1;
 
    // if already solved then
    // return result directly
    if (memo[N, K] != 0)
        return memo[N, K];
 
    // calling recursively all
    // subproblem of permutation
    // size N - 1
    int sum = 0;
    for (int i = 0; i <= K; i++)
    {
         
        // Call recursively only if
        // total inversion to be
        // made are less than size
        if (i <= N - 1)
            sum += numberOfPermWithKInversion(N - 1,
                                              K - i);
    }
 
    // store result into memo
    memo[N, K] = sum;
 
    return sum;
}
 
// Driver Code
static public void Main ()
{
    int N = 4;
    int K = 2;
    Console.WriteLine(numberOfPermWithKInversion(N, K));
}
}
 
// This code is contributed by ajit

PHP

<?php
// PHP program to find number of permutation
// with K inversion using Memoization
 
// method recursively calculates
// permutation with K inversion
function numberOfPermWithKInversion($N, $K)
{
     
    $memo = array();
     
    // base cases
    if ($N == 0)
        return 0;
    if ($K == 0)
        return 1;
 
    // if already solved then
    // return result directly
    if ($memo[$N][$K] != 0)
        return $memo[$N][$K];
 
    // calling recursively all subproblem
    // of permutation size N - 1
    $sum = 0;
    for ($i = 0; $i <= $K; $i++)
    {
 
        // Call recursively only
        // if total inversion
        // to be made are less
        // than size
        if ($i <= $N - 1)
            $sum += numberOfPermWithKInversion($N - 1,
                                               $K - $i);
    }
 
    // store result into memo
    $memo[$N][$K] = $sum;
 
    return $sum;
}
 
// Driver code
$N = 4;
$K = 2;
echo numberOfPermWithKInversion($N, $K);
 
// This code is contributed
// by Akanksha Rai(Abby_akku)
?>

Javascript

<script>
 
// Javascript program to find number of
// permutation with K inversion using
// Memoization
 
// Limit on N and K
let M = 100;
 
// 2D array memo for stopping solving
// same problem again
let memo = new Array(M);
for(let i = 0; i < M; i++)
{
    memo[i] = new Array(M);
    for(let j = 0; j < M; j++)
    {
        memo[i][j] = 0;
    }
}
 
// Method recursively calculates permutation
// with K inversion
function numberOfPermWithKInversion(N, K)
{
     
    // base cases
    if (N == 0)
        return 0;
    if (K == 0)
        return 1;
 
    // If already solved then return
    // result directly
    if (memo[N][K] != 0)
        return memo[N][K];
 
    // Calling recursively all subproblem of
    // permutation size N - 1
    let sum = 0;
    for(let i = 0; i <= K; i++)
    {
         
        // Call recursively only if total inversion
        // to be made are less than size
        if (i <= N - 1)
            sum += numberOfPermWithKInversion(
                N - 1, K - i);
    }
     
    // Store result into memo
    memo[N][K] = sum;
 
    return sum;
}
 
// Driver code
let N = 4;
let K = 2;
 
document.write(numberOfPermWithKInversion(N, K));
 
// This code is contributed by divyesh072019 
 
</script>
Producción

5

Complejidad de tiempo: O(N*N*K)

Complejidad espacial: O(N*K)

Enfoque optimizado: uso de tabulación y suma acumulada

C++

// C++ program to find number of permutation
// with K inversions
 
#include <bits/stdc++.h>
using namespace std;
 
int numberOfPermWithKInversions(int N, int K) {
    vector<vector<int>> dp(N+1,vector<int>(K+1));
   
    // As for k=0, number of permutations is 1 for every N
      for(int i = 1; i <= N; i++)
        dp[i][0] = 1;
 
      // Using Dynamic Programming with cumulative sum
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= K; j++)
        {
              // This is same as val = dp[i-1][j] - dp[i-1][j-i]
              // i.e. dp[i-1][j........j-i], just taking care of
              // boundaries
            int val = dp[i-1][j];
            if(j >= i)
                val -= dp[i-1][j-i];
 
            dp[i][j] = dp[i][j-1] + val;
        }
    }
   
      // And, in the end calculate the dp[n][k]
      // which is dp[n][k]-dp[n][k-1]
    int ans = dp[N][K];
    if(K >= 1)
        ans -= dp[N][K-1];
 
    return ans;
}
 
int main() {
    int N = 4;
    int K = 2;
     
      cout << numberOfPermWithKInversions(N,K) << "\n";
    return 0;
}

Java

/*package whatever //do not write package name here */
 
import java.io.*;
 
class GFG {
    static int numberOfPermWithKInversion(int N, int K)
    {
       int[][] dp = new int[N + 1][K + 1];
       for(int i = 1; i <= N; i++)
        dp[i][0] = 1;
 
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= K; j++)
        {
              // boundaries
            int val = dp[i-1][j];
            if(j >= i)
                val -= dp[i-1][j-i];
  
            dp[i][j] = dp[i][j-1] + val;
        }
    }
    
      // And, in the end calculate the dp[n][k]
      // which is dp[n][k]-dp[n][k-1]
    int ans = dp[N][K];
    if(K >= 1)
        ans -= dp[N][K-1];
  
    return ans;
    }
   
    public static void main (String[] args) {
        int N = 4;
        int K = 2;
        System.out.println(numberOfPermWithKInversion(N, K));
    }
}
Producción

5

Complejidad de tiempo: O(N*K)

Complejidad espacial: O(N*K)
Este artículo es una contribución de Utkarsh Trivedi y Ankit Kumar Sharma . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *