Suppose that we have an array with arrayLength distinct elements.
A quite common task in programming is to randomly permute this array.
Novices who encounter this situation often implement the following algorithm:
- Choose a positive integer swapCount.
- swapCount times randomly choose two distinct indices and swap the corresponding elements.
This method of permuting an array is bad, because some permutations of the array will be more likely than others.
In this problem, you shall compute how bad this method is for a given situation.
You will be given four ints: arrayLength, swapCount, a and b.
Consider the element of the array that initially had the index a.
Write a method that will compute the probability that this element will have the index b at the end of the process described above.