Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Intuition
4.
Brute Force Approach
5.
Program
5.1.
Example
6.
Using Memoization
7.
Program
7.1.
Example
8.
Complexity Analysis
9.
Key Takeaways:
Last Updated: Mar 27, 2024

Expected Swaps to Sort an Array when Probability of Swapping for Every Inversion Pair is Equal

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

We all prepare Data Structures and Algorithms to crack interviews of our dream company. A data structure that can not be neglected while this preparation is Arrays. Along with data structures, concepts of mathematics like expected value and probability are very often asked in interviews.

Let’s learn these concepts together with the help of a problem.  

Problem Statement

A permutation of numbers from 1 to ‘N’ stored in an array nums[], is given. You are asked to find the expected number of swaps to sort ‘nums’, when

  • The probability of swapping any inversion pair is equal
  • The probability of swapping any non-inversion pair is zero


Inversion pair can be explained as a pair of two indices i, j where i < j and nums[i] > nums[j]

Example

Input: nums[] = {2, 1, 3, 4}

Output: 1.0

Explanation: In the above array, there is only one inversion pair: {nums[0], nums[1]}

So the expected value will be:  1 / 1 = 1.0


Input: nums[] = {1, 4, 3, 2}

Output: 2.333

Explanation: In the above array, there are the following three inversion pairs:

  1. {nums[1], nums[2]}: After swapping-
    Expected number of swaps: 1 + (2 + 2) / 2 = 3.0
     
  2. {nums[1], nums[3]}: After swapping-
    Expected number of swaps: 1 / 1 = 1.0
     
  3. {nums[2], nums[3]}: After swapping-   
    Expected number of swaps: 1 + (2 + 2) / 2 = 3.0

    So expected number of swaps for the above array: (1 + 3 + 3) / 3 = 7 / 3 = 2.333
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

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

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!

 

Previous article
Count of subsets with sum equal to X
Next article
Longest Increasing Path in a Matrix
Live masterclass