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));
}
}
Producción
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