Dada una array arr[] que consiste en la permutación de los primeros N números naturales , la tarea es encontrar el número esperado de intercambios para ordenar la array dada donde la probabilidad de intercambiar cualquier par de inversión es igual y la probabilidad de intercambiar cualquier par que no sea inversión el par es 0
Ejemplos:
Entrada: arr[] = {3, 2, 1}
Salida: 2.3333
Explicación: La array dada se puede ordenar en orden no decreciente usando secuencias de intercambios como se muestra en la imagen a continuación.
El número esperado de intercambios de cada Node se puede calcular mediante 1 + (promedio del número esperado de intercambios de todos los Nodes secundarios).
Dado que los Nodes 3, 9, 10, 11 y 12 ya están ordenados, el número de intercambios esperados para ordenarlos es 0.
El número esperado de intercambios de los Nodes 5, 6, 7 y 8 será 1.
De manera similar, el el número esperado de intercambios de los Nodes 2 y 4 será 2.
Por lo tanto, el número esperado de intercambios del Node 1 es 1 + (2 + 2 + 0)/3 = 1 + 1.3333 = 2.3333Entrada: arr[] = {1, 3, 2}
Salida: 1.0
Explicación: Dado que solo hay 1 par de inversión (arr[1], arr[2]), el número esperado de intercambios es 1.
Enfoque: el problema dado se puede resolver con la ayuda de la recursividad y el retroceso mediante la memorización, que se basa en las siguientes observaciones:
- Una inversión en la array se define como dos índices (i, j) tales que i < j y arr[i] > arr[j] . El número esperado de intercambios se puede calcular recursivamente después de intercambiar los enteros de cada inversión válida uno a la vez y llamando recursivamente a la permutación después del intercambio hasta que se ordene toda la permutación.
- Supongamos que hay K inversiones en la permutación actual y después de intercambiar la i -ésima inversión, el número esperado de intercambios para ordenar la permutación se denota por P i . Por lo tanto, el número esperado de intercambios después de intercambiar todas las inversiones posibles será (P 1 + P 2 + … + P K )/K .
Usando las observaciones anteriores, el problema dado se puede resolver mediante los siguientes pasos:
- Cree un mapa , digamos una nota que almacene el número esperado de intercambios para una permutación dada.
- Cree una función recursiva expectedSwaps() , que toma una permutación como argumento y devuelve el número esperado de intercambios.
- En la función ExpectedSwaps() , si ya se calcularon los intercambios esperados de la permutación actual, devuelve la respuesta. De lo contrario, itere sobre cada inversión válida e intercambie el índice de la inversión actual y llame recursivamente a la permutación después del intercambio.
- Encuentre la suma de los intercambios esperados después de cada intercambio válido en una variable, digamos res , y el recuento de inversiones en una variable, digamos K .
- Después de completar los pasos anteriores, imprima el valor de res / K 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; // Stores result of each state of the // array in a memoization table map<vector<int>, double> memo; // Recursive function to find expected // number of swaps to sort given array double expectedSwaps(vector<int> a) { // The value for the given permutation // is already calculated if (memo.count(a)) { return memo[a]; } // Stores the expected number of ways double res = 0; // Stores the total operations done int K = 0; // Iterate for all possible pairs of // Inversions for (int i = 0; i < a.size(); i++) { for (int j = i + 1; j < a.size(); j++) { // For the current inversion // find the expected value if (a[i] > a[j]) { swap(a[i], a[j]); // Recursively Call res += 1 + expectedSwaps(a); // Backtrack swap(a[i], a[j]); K++; } } } // If permutation is already sorted if (K == 0) res = 0; // Calculate expected swaps for // current permutation else res /= K; // Return answer return memo[a] = res; } // Driver Code int main() { int N = 3; vector<int> arr = { 3, 2, 1 }; cout << expectedSwaps(arr); return 0; }
Java
// Java code for the above approach: import java.util.*; public class Main { // Stores result of each state of the // array in a memoization table static HashMap <ArrayList <Integer>, Double> memo; // Recursive function to find expected // number of swaps to sort given array static double expectedSwaps(ArrayList <Integer> a) { // The value for the given permutation // is already calculated if (memo.containsKey(a)) { return memo.get(a); } // Stores the expected number of ways double res = 0; // Stores the total operations done int K = 0; // Iterate for all possible pairs of // Inversions for (int i = 0; i < a.size(); i++) { for (int j = i + 1; j < a.size(); j++) { // For the current inversion // find the expected value if (a.get(i) > a.get(j)) { Collections.swap(a, i, j); // Recursively Call res += 1 + expectedSwaps(a); // Backtrack Collections.swap(a, i, j); K++; } } } // If permutation is already sorted if (K == 0) res = 0; // Calculate expected swaps for // current permutation else res /= K; // Return answer memo.put(a,res); return res; } // Driver Code public static void main(String args[]) { int N = 3; ArrayList <Integer> arr = new ArrayList <Integer> (Arrays.asList( 3, 2, 1 )); memo = new HashMap <ArrayList <Integer>, Double> (); // Function calling System.out.println( expectedSwaps(arr) ); } } // This code has been contributed by Sachin Sahara (sachin801)
Python3
# Python program for the above approach # Stores result of each state of the # array in a memoization table memo = {} # Recursive function to find expected # number of swaps to sort given array def expectedSwaps(a): # The value for the given permutation # is already calculated if (tuple(a) in memo): return memo[tuple(a)] # Stores the expected number of ways res = 0 # Stores the total operations done K = 0 # Iterate for all possible pairs of # Inversions for i in range(len(a)): for j in range(i + 1,len(a)): # For the current inversion # find the expected value if (a[i] > a[j]): temp = a[i] a[i] = a[j] a[j] = temp # Recursively Call res += 1 + expectedSwaps(a) #Backtrack temp = a[i] a[i] = a[j] a[j] = temp K += 1 # If permutation is already sorted if (K == 0): res = 0 # Calculate expected swaps for # current permutation else: res /= K; # Return answer memo[tuple(a)] = res return res # Driver Code N = 3 arr = [ 3, 2, 1 ] print(expectedSwaps(arr)) # This code is contributed by rohitsingh07052.
Javascript
<script> // JavaScript program for the above approach // Stores result of each state of the // array in a memoization table var dict = {}; // Recursive function to find expected // number of swaps to sort given array function expectedSwaps(a) { // The value for the given permutation // is already calculated if (dict.hasOwnProperty(a)) { return dict[a]; } // Stores the expected number of ways var res = 0; // Stores the total operations done var K = 0; // Iterate for all possible pairs of // Inversions for (let i = 0; i < a.length; i++) { for (let j = i + 1; j < a.length; j++) { // For the current inversion // find the expected value if (a[i] > a[j]) { var temp = a[i]; a[i] = a[j]; a[j] = temp; // Recursively Call res += 1 + expectedSwaps(a); // Backtrack var temp2 = a[i]; a[i] = a[j]; a[j] = temp2; K++; } } } // If permutation is already sorted if (K == 0) { res = 0; } // Calculate expected swaps for // current permutation else { res /= K; } // Return answer dict[a] = res; return res; } // Driver Code var N = 3; var arr = [3, 2, 1]; document.write(expectedSwaps(arr).toFixed(5)); // This code is contributed by rdtank. </script>
C#
// C# program to implement above approach using System; using System.Collections.Generic; class GFG { // Stores result of each state of the // array in a memoization table public static Dictionary<List<int>, double> memo = new Dictionary<List<int>, double>(); public static bool checkEquality(List<int> a,List<int> b){ if(a.Count != b.Count) return false; for(int i = 0 ; i < a.Count ; i++){ if(a[i]!=b[i]) return false; } return true; } public static double containsKey(List<int> a){ foreach(KeyValuePair<List<int>,double> x in memo){ if(checkEquality(a, x.Key)){ return x.Value; } } return -1; } // Recursive function to find expected // number of swaps to sort given array public static double expectedSwaps(List<int> a) { // The value for the given permutation // is already calculated double res = containsKey(a); if (res != -1) { return res; } // Stores the expected number of ways res = 0; // Stores the total operations done int K = 0; // Iterate for all possible pairs of // Inversions for (int i = 0 ; i < a.Count ; i++) { for (int j = i + 1 ; j < a.Count ; j++) { // For the current inversion // find the expected value if (a[i] > a[j]) { int temp = a[i]; a[i] = a[j]; a[j] = temp; // Recursively Call res += 1 + expectedSwaps(a); // Backtrack temp = a[i]; a[i] = a[j]; a[j] = temp; K++; } } } // If permutation is already sorted if (K == 0) res = 0; // Calculate expected swaps for // current permutation else res = res/(double)K; // for(int i=0 ; i<a.Count ; i++){ // Console.Write(a[i] + " "); // } // Console.Write("\n" + res + "\n"); memo[new List<int>(a)] = res; // Return answer return res; } // Driver Code public static void Main(string[] args){ // int N = 3; List<int> arr = new List<int>{ 3, 2, 1 }; Console.Write(expectedSwaps(arr)); } }
2.33333
Complejidad de Tiempo: O(N 2 N!)
Espacio Auxiliar: O(N!)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA