Determine the probability, Such that array A is sorted after applying exactly $N$ swap operations on array $A.$

combinationsdata structurepermutationsprobabilitysorting

You have an array $A$ of size $6$, which is a permutation of numbers $1 \dots 6$. Apply exactly $N$ operations on this array $A$.

In one operation:

  1. You choose two distinct numbers in array $A$ randomly and swap them.

Determine the probability, such that array $A$ is sorted after applying exactly $N$ described operations on array $A$.

Examples

  1. $N = 0$
    $A = \{ 1, 2, 3, 4, 5, 6 \}$
    After $0$ operations the array is sorted, hence the probability is $1$.
  2. $N = 1$
    $A = \{ 2, 1, 3. 4, 5, 6 \}$
    There are $15$ possible operations that can be applied on array $A$, out of which only $1$ operation (swap 1 and 2) yields a sorted array. Hence the required probability is $1 / 15$.
  3. $N = 5$
    $A = \{ 1, 5, 4, 2, 3, 6 \}$
    There are 759375 possible sets of 5 operations that can be applied on array A, out of which only 2848 sets of operations yield a sorted array. Hence the required probability is $2848 / 759375$.

My starting approach

The way I am approaching the solution is as follow

I think there is some kind of maths behind it because there are only 10 possible configurations of Array,

following numbers are the number of misplaced numbers

  1. 0+2
  2. 3+0
  3. 4+0
  4. 0+4
  5. 2+2
  6. 5+0
  7. 3+2
  8. 6+0
  9. 0+6
  10. 4+2

The right values indicate the number of numbers that have a pair that brings both numbers to their correct position after just one swap for example 2 1 3 4 5 6, here 1 and 2 can be swapped and after just one swap 1 and 2 will be at their correct positions and the array will become 1 2 3 4 5 6

The left values are the opposite of right values for example 2 3 1 4 5 6, here 1 2 3 belongs to the left numbers,

All of those 10 possible cases will have the same answers for each value for N, no matter which numbers are at wrong positions. for example Array 2 1 3 4 5 6 is going to have the same answer for all possible values of N as an array 1 2 4 3 5 6 because both arrays belong to 1st possibility which is 0+2 out of those 10 possible cases.

For example

$A = 2 1 3 4 5 6$

Answers for the given array is follow

$n = 1$ then $1/15$

$n = 3$ then $51/3375$

$n = 5$ then $4821/759375$

$n = 7$ then $679910/170859375$

for $n = 2, 4, 6, 8$ answer is $0$.

The total possible set of operations are $15^n$

Best Answer

This was a programming problem asked on HackerEarth. I will address it as a programming problem rather than a Mathematical one.

We have to write code that runs for the given input in under $1$ second.

You are given a permutation of $6$ elements and an integer $N$. Give the probability that the permutation will be sorted after exactly $N$ swaps. $$1 \le N \le 100$$ If the probability is $\frac{P}{Q}$, where $P, Q$ are integers in the reduced form, print $P \cdot Q^{-1} \pmod {10^9 + 7}$

The general rule of thumb in any programming problem is that the computer can perform $10^7$ instructions per second and the time limit is usually $1$ second. Hence, any code we write must be able to obtain the answer in fewer than $10^7$ computer instructions.

Recurrence

Let $P(A, i)$ be the probability of sorting an array $A$ in exactly $i$ moves.

Let $A'$ be an array that we can obtain from $A$ in exactly one swap. In any array $A$, we can make $\binom{6}{2} = 15$ swaps. $$P(A, i) = \frac{1}{\binom{6}{2}}\sum P(A', i - 1)$$

Explanation of the Recurrence

We know that the probability of an event is the size of the the event set divided by the size of the total space set.

In order to know the probability of sorting an array $A$ in $i$ moves, we need to know the probability of sorting $A'$ in $i - 1$ moves, and then divide by the number of different arrays we can get in $1$ move.

For example, from ${1, 2, 3}$, we can transition to $3$ different arrays with swaps.

  1. $\{1, 2, 3\} \to \{2, 1, 3\}$
  2. $\{1, 2, 3\} \to \{3, 2, 1\}$
  3. $\{1, 2, 3\} \to \{2, 1, 3\}$

In order to know the probability of sorting $\{1, 2, 3\}$ in $x$ moves, we need to add the probability of sorting these $3$ arrays in $x - 1$ moves and divide by $3$

The probabability of sorting an array $\{1, 2, 3\}$ in $2$ moves is $$P(\{1, 2, 3\}, 2) = \frac{1}{3} \cdot \big( P(\{1, 3, 2\}, 1) + P(\{2, 1, 3\}, 1) + P(\{3, 2, 1\}, 1) \big)$$

Space and Time Complexity

Let us now try to estimate the time and space complexity. How many states does this DP have ? We have $6! = 720$ different arrays and $$N = 100$$ moves. So, we will have $720 \times 100$ different states.

How many transitions are there in each state ? Each state has $\binom{6}{2} = 15$ transitions.

The total number of steps is roughly $720 \times 100 \times 15 \approx 10^7$

C++ Code

Here is a function which computes the probability of sorting an array with $N$ random swaps. For convenience, I have stored the array as a string.

I used Fermat's Little Theorem to compute the modular inverse of the denominator. $$x^{m - 1} = 1 \pmod m \implies x \cdot x^{m - 2} = 1 \pmod m$$

#include<bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7, NO_OF_ELEMENTS = 6;
map <pair <string, int>, long long> probability;

long long power_mod(long long x, long long p, long long m)
{
    long long answer = 1; 

    while(p > 0)
    {
        if(p%2 == 1)
        {
            answer = (answer*x)%m;
        }

        x = (x*x)%m;
        p = p >> 1;
    }

    return answer;
}

long long inverse(long long x, long long m)
{
    return power_mod(x, m - 2, m);
}

int is_sorted(string S)
{
    for(int i = 0; i + 1 < NO_OF_ELEMENTS; i++)
    {
        if(S[i] > S[i + 1])
        {
            return false;
        }
    }

    return true;
}

long long get_probability(string S, int no_of_moves)
{
    pair <string, int> current_state = make_pair(S, no_of_moves);
    if(probability.find(current_state) != probability.end())
    {
        return probability[current_state];
    }

    if(no_of_moves == 0)
    {
        probability[current_state] = (is_sorted(S) ? 1 : 0);
        return probability[current_state];
    }

    long long numerator = 0, new_arrays = 0;
    for(int i = 0; i < NO_OF_ELEMENTS; i++)
    {
        for(int j = i + 1; j < NO_OF_ELEMENTS; j++)
        {
            string new_S = S;
            swap(new_S[i], new_S[j]);

            numerator += get_probability(new_S, no_of_moves - 1);
            new_arrays++;
        }
    }

    probability[current_state] = numerator*inverse(new_arrays, MOD);
    probability[current_state] %= MOD;

    return probability[current_state];
}

void solve()
{
    int no_of_moves;
    cin >> no_of_moves;

    vector <int> A(NO_OF_ELEMENTS);
    for(int i = 0; i < NO_OF_ELEMENTS; i++)
    {
        cin >> A[i];
    }

    string S; 
    for(int i = 0; i < NO_OF_ELEMENTS; i++)
    {
        S += A[i];
    }

    cout << get_probability(S, no_of_moves) << "\n";
}

int main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int no_of_test_cases; 
    cin >> no_of_test_cases; 

    while(no_of_test_cases--)
        solve();

    return 0;
}
Related Question