Denote the probability for sorting the n numbers in one go by Pr(n).
In the first pass of Bubble sort, we can definitely say that the largest number has reached the end position. So now there arises two cases:
1. Where the largest number 'n' is already at the last position. This means we are effectively solving the problem for (n - 1) numbers.
2. Where the largest number occurs somewhere in the middle. In this case, if the bubble sort has to sort the array in one go, the part of the array coming before n should also get sorted in one go and the part of the array after n should already be sorted.
Now, we create a summation.
Pr(n) = Summation ( Pr(x) * (x!/n!) ) where the summation index 'x' goes from 0 to n - 1. 'x' denotes the number of numbers on the left side of 'n' in the array.
How to arrive at this expression?
Consider 'n' at a position such that there are 'x' numbers on the left side of 'n'. Probability that the array gets sorted in one go should imply that the numbers on the right side should already be sorted and the numbers on the left side should get sorted in one go too. Note that all these 'x' numbers should be smaller than n and after the Bubble sort pass should get sorted themselves. So we are essentially solving Pr(x).
Pr(array gets sorted in one go provided 'x' numbers are there on the left side of n) = Pr(such permutation occurs) * Pr(x)
= (x!/n!) * Pr(x)
For Pr(n) we will have to iterate for all the positions where n can occur.
Pr(n) = (1/n) * Pr(n - 1) + Summation ( Pr(x) * (x!/n!) ) , where the summation index now goes from x = 0 to x = n - 2
Taking (1/n) common from the Summation above makes it nothing but Pr(n-1).
Pr(n) = (1/n) * Pr(n - 1) + (1/n) * Pr(n-1)
Pr(n) = (2/n) * Pr(n-1)
We now have a recursive solution. Just keep expanding the Pr() that occur till Pr(3). Note that Pr(0) = Pr(1) = Pr(2) = 1.
Pr(n) = (2/n) * (2/n-1) * (2/n-2) .... 2/3
Pr(n) = 2^(n-1) / n! [Multiply and divide by 2 to make the denominator n!]
Once I read the above solution all the below solutions became intuitive on their own. These solutions don't in particular offer any extra insight more than the original solution. The interviewer would really like us to think in a crisp and structured manner, and it can't get more crisp than the former.
We use dynamic programming. Let dp[i] = number of possible permutations of size i, which satisfy this property. Consider first element of this permutation:
1. case 1: It is a 1. then ans is dp[i-1].
2. case 2: It is not a 1. Suppose it is x. then note that the permutation must look like x,1,2,3,...,x-1 , [ something ] (why?). Hence ans is dp[i-x+1].
Thus dp[i] = dp[i-1] + dp[i-2] +...+ dp[1] equivalent to dp[i] = 2*dp[i-1] with dp[1] = 1. Thus done.
My approach:
We take a sorted array and start to dearrange it from the last. Just the opposite of how bubble sort works.
Firstly, we go to the nth element and see that we have 2 options, either leave it as it is. Or swap it with the n-1th element.
Then we go to (n-1)th element and again we have 2 options.
This goes on until we reach the second element. For the first element there is no 0th element to swap.
So, we end up with required possible arrangements = 2*2*2*2*.... (n-1)times = 2^(n-1)
And as total possible arrangements= n!
We get to the 2^(n-1)/n!
My approach:
Denote the probability for sorting the n numbers in one go by Pr(n).
In the first pass of Bubble sort, we can definitely say that the largest number has reached the end position. So now there arises two cases:
1. Where the largest number 'n' is already at the last position. This means we are effectively solving the problem for (n - 1) numbers.
2. Where the largest number occurs somewhere in the middle. In this case, if the bubble sort has to sort the array in one go, the part of the array coming before n should also get sorted in one go and the part of the array after n should already be sorted.
Now, we create a summation.
Pr(n) = Summation ( Pr(x) * (x!/n!) ) where the summation index 'x' goes from 0 to n - 1. 'x' denotes the number of numbers on the left side of 'n' in the array.
How to arrive at this expression?
Consider 'n' at a position such that there are 'x' numbers on the left side of 'n'. Probability that the array gets sorted in one go should imply that the numbers on the right side should already be sorted and the numbers on the left side should get sorted in one go too. Note that all these 'x' numbers should be smaller than n and after the Bubble sort pass should get sorted themselves. So we are essentially solving Pr(x).
Pr(array gets sorted in one go provided 'x' numbers are there on the left side of n) = Pr(such permutation occurs) * Pr(x)
= (x!/n!) * Pr(x)
For Pr(n) we will have to iterate for all the positions where n can occur.
Pr(n) = (1/n) * Pr(n - 1) + Summation ( Pr(x) * (x!/n!) ) , where the summation index now goes from x = 0 to x = n - 2
Taking (1/n) common from the Summation above makes it nothing but Pr(n-1).
Pr(n) = (1/n) * Pr(n - 1) + (1/n) * Pr(n-1)
Pr(n) = (2/n) * Pr(n-1)
We now have a recursive solution. Just keep expanding the Pr() that occur till Pr(3). Note that Pr(0) = Pr(1) = Pr(2) = 1.
Pr(n) = (2/n) * (2/n-1) * (2/n-2) .... 2/3
Pr(n) = 2^(n-1) / n! [Multiply and divide by 2 to make the denominator n!]
Once I read the above solution all the below solutions became intuitive on their own. These solutions don't in particular offer any extra insight more than the original solution. The interviewer would really like us to think in a crisp and structured manner, and it can't get more crisp than the former.
Cheers!!
Another solution:
We use dynamic programming. Let dp[i] = number of possible permutations of size i, which satisfy this property. Consider first element of this permutation:
1. case 1: It is a 1. then ans is dp[i-1].
2. case 2: It is not a 1. Suppose it is x. then note that the permutation must look like x,1,2,3,...,x-1 , [ something ] (why?). Hence ans is dp[i-x+1].
Thus dp[i] = dp[i-1] + dp[i-2] +...+ dp[1] equivalent to dp[i] = 2*dp[i-1] with dp[1] = 1. Thus done.