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>
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)); } }
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