RandomShuffle | Topcoder Archive

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

Class:: RandomShuffle
Method:: probability
Parameters:: int[]
Returns:: double
Method signature:: double probability(int[] outputArray)
(be sure your method is public)

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

```
{1}
```
```
Returns: 1.0
```
```
{1,2}
```
```
Returns: 0.5
```
"swap A[1] and A[1], swap A[2] A[2]" or "swap A[1] and A[2], swap A[2] and A[1]" in the shuffle function will both lead to the outcome {1,2}.
```
{1,3,2}
```
```
Returns: 0.1851851851851852
```

{4,2,5,1,3}

Returns: 0.006720000000000001

```
{4,6,9,3,5,8,10,1,7,2}
```
```
Returns: 2.825E-7
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.