Intuition
The above conditions signify that, after swapping any inversion pair, the resulting array will be again an array that needs swaps to make it sorted. This gives us a hint for a recursive approach. So we can calculate the expected value of swaps by counting the number of swaps for every state of the array generated with the help of recursion and Backtracking.
Brute Force Approach
The complete solution can be understood with the help of the below algorithm.
- Function swapsExpected() will be used to return the expected value for a given state of the vector nums.
- In function swapsExpected(), first, we will check if the vector in the argument has already been evaluated; if yes, we can simply return.
- Else we will run two for loops with indices i, j and search for the inversion pairs. For every inversion pair, we will swap the elements at index i and j and recursively find the expected value for the resultant vector.
- Finally record the expected value of the vector by dividing the sum of recorded expected values with cnt, the number of inversion pairs.
The implementation of the above algorithm can be found in the below program.
Program
// Program to find the expected number of swaps for the given array.
#include <iostream>
#include <vector>
#include <map>
using namespace std;
// Function to find the expected value of swaps for the given vector.
double swapsExpected(vector<int> nums)
{
// Variable to store the count of inversion pairs.
int cnt = 0;
// Variable to store the expected value of the current vector.
double exp = 0;
// Finding the expected value after swapping each inversion pair.
for (int i = 0; i < nums.size(); i++)
{
for (int j = i + 1; j < nums.size(); j++)
{
// Checking if the current pair is an inversion pair.
if (nums[i] < nums[j])
continue;
// Increasing the count of pairs of inversion.
cnt++;
// Swapping the inversion pairs.
swap(nums[i], nums[j]);
// Calling the function recursively for the new state of nums and taking the sum of the expected value.
exp = exp + 1 + swapsExpected(nums);
// Reverting the changes for backtracking.
swap(nums[i], nums[j]);
}
}
// If the number of inversion pairs is zero.
if (!cnt)
exp = 0;
else
exp = exp / double(cnt);
// returning the expected swaps for the vector ‘nums’.
return exp;
}
// Main function.
int main()
{
// Input the size of the vector, ‘nums’.
int N; cin >> N;
// Input vector ‘nums’.
vector<int> nums(N);
for (int i = 0; i < N; i++)
cin >> nums[i];
// Calling function swapExpected() to calculate the expected swaps and storing the answer.
double ans = swapsExpected(nums);
// Output for the final result.
cout << "Expected number of swaps is: " << ans;
return 0;
}
You can also try this code with Online C++ Compiler
Example
Input
7
5 4 1 3 2 6 7
Output
Expected number of swaps is: 5.63175
Using Memoization
To remove the repetitions of the queries, we can use a map to store the evaluated queries.
- rec, map from vector to double will be used to record the evaluated queries.
Program
// Program to find the expected number of swaps for the given array.
#include <iostream>
#include <vector>
#include <map>
using namespace std;
// Map to record the evaluated values.
map<vector<int>, double> rec;
// Function to find the expected value of swaps for the given vector.
void swapsExpected(vector<int> nums)
{
// Checking if the expected value has already been recorded.
if (rec.count(nums))
return;
// Variable to store the count of inversion pairs.
int cnt = 0;
// Variable to store the expected value of the current vector.
double exp = 0;
// Finding the expected value after swapping each inversion pair.
for (int i = 0; i < nums.size(); i++)
{
for (int j = i + 1; j < nums.size(); j++)
{
// Checking if the current pair is an inversion pair.
if (nums[i] < nums[j])
continue;
// Increasing the count of pairs of inversion.
cnt++;
// Swapping the inversion pairs.
swap(nums[i], nums[j]);
// Calling the function recursively for the new state of nums.
swapsExpected(nums);
// Taking sum of the expected value
exp = exp + 1 + rec[nums];
// Reverting the changes for backtracking.
swap(nums[i], nums[j]);
}
}
// If the number of inversion pairs is zero.
if (!cnt)
exp = 0;
else
exp = exp / double(cnt);
// recording the expected swaps for the vector ‘nums’.
rec[nums] = exp;
}
// Main function.
int main()
{
// Input the size of the vector, ‘nums’.
int N; cin >> N;
// Input vector ‘nums’.
vector<int> nums(N);
for (int i = 0; i < N; i++)
cin >> nums[i];
// Calling function swapExpected() to calculate the expected swaps.
swapsExpected(nums);
// Storing the answer.
double ans = rec[nums];
// Output for the final result.
cout << "Expected number of swaps is: " << ans;
return 0;
}
You can also try this code with Online C++ Compiler
Example
Input
5
5 4 1 3 2
Output
Expected number of swaps is: 5.63175
Complexity Analysis
Time Complexity: O(N2 x N!)
Explanation:
- In the worst-case scenario, we will have (N-1)! inversion pairs
- After each swap of inversion pair, the new vector generated will require two nested loops to find the expected swaps, taking the time of O(N2)
- Constituting the complexity of O(N! X N!)
Space Complexity: O(N!)
Explanation:
- In the worst-case scenario, for (N-1)! inversion pairs, (N-1)! new vectors will be generated, which will occupy the memory of O(N x (N-1)!) or O(N!)
Check out this problem - Count Inversions
Key Takeaways:
The above blog discussed an interesting question that involves the concepts of arrays, mathematics - expected value, recursion, and backtracking together. ‘Expected Swaps to Sort an Array when Probability of Swapping for Every Inversion Pair is Equal’ is also an important problem from the interview point of view, where you can be tested for many concepts simultaneously.
Recommended Problems -
If you want to learn more about such problems, head over to our library section for many such interesting blogs. Keep learning.
Happy Coding!
569+ registered 
