Problem Statement | |||||||||||||
A random shuffle function is described in the pseudocode below:
N=length of array A For i=1 to N Generate a uniform random integer r between 1 and N inclusive Swap A[i] and A[r] Return the probability that the int[] outputArray was produced by performing the shuffle function on the int[] {1, 2, 3, ..., N}, where N is the number of elements in outputArray. | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Notes | |||||||||||||
- | A uniform random number between 1 and N, inclusive, is one where each number between 1 and N, inclusive, has the same probability of being generated. | ||||||||||||
- | The returned value must be accurate to within a relative or absolute value of 1E-9. | ||||||||||||
Constraints | |||||||||||||
- | outputArray will contain between 1 and 10 elements, inclusive. | ||||||||||||
- | Each element of outputArray will be between 1 and N, inclusive, where N is the number of elements in outputArray. | ||||||||||||
- | The elements of outputArray will be distinct. | ||||||||||||
Examples | |||||||||||||
0) | |||||||||||||
| |||||||||||||
1) | |||||||||||||
| |||||||||||||
2) | |||||||||||||
| |||||||||||||
3) | |||||||||||||
| |||||||||||||
4) | |||||||||||||
|