TopCoder Statistics - Problem Statement

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}.
{2,1}

Returns: 0.5
{1,2}

Returns: 0.5
{1,2}

Returns: 0.5
{1,2}

Returns: 0.5
{1,3,2}

Returns: 0.1851851851851852
{3,1,2}

Returns: 0.14814814814814814
{1,2,3}

Returns: 0.14814814814814814
{1,2,3}

Returns: 0.14814814814814814
{1,2,3}

Returns: 0.14814814814814814
{3,1,4,2}

Returns: 0.04296875
{2,3,1,4}

Returns: 0.0546875
{3,4,2,1}

Returns: 0.0390625
{2,1,4,3}

Returns: 0.05859375
{1,3,2,4}

Returns: 0.0390625
{3,2,4,5,1}

Returns: 0.010559999999999998
{3,5,1,2,4}

Returns: 0.00928
{1,4,2,5,3}

Returns: 0.01024
{4,2,5,1,3}

Returns: 0.006720000000000001
{5,1,3,4,2}

Returns: 0.0057599999999999995
{5,3,6,4,1,2}

Returns: 0.0011145404663923182
{1,6,4,3,2,5}

Returns: 0.0010931069958847737
{4,2,6,3,1,5}

Returns: 0.0012217078189300412
{1,4,2,5,3,6}

Returns: 0.0013717421124828531
{5,1,6,2,3,4}

Returns: 0.0011145404663923182
{7,2,6,5,1,3,4}

Returns: 1.457118814682415E-4
{7,1,4,5,2,3,6}

Returns: 1.4814041282604549E-4
{6,2,5,4,3,7,1}

Returns: 1.687829293673797E-4
{6,5,1,2,7,4,3}

Returns: 1.6756866368847773E-4
{3,7,4,1,6,5,2}

Returns: 1.9913957133993004E-4
{6,2,5,3,8,1,7,4}

Returns: 2.110004425048828E-5
{1,5,4,6,8,3,7,2}

Returns: 2.765655517578125E-5
{1,6,2,8,4,5,3,7}

Returns: 2.0563602447509766E-5
{1,8,5,7,3,2,6,4}

Returns: 1.8298625946044922E-5
{8,5,1,2,7,6,4,3}

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

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

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

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

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

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

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

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

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

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

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

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

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

Returns: 7.722E-7
{1, 3, 2 }

Returns: 0.1851851851851852
{4, 6, 9, 3, 5, 8, 10, 1, 7, 2 }

Returns: 2.825E-7

Statistics

Problem Statement for "RandomShuffle"

Problem Statement

Definition

Notes

Constraints

Examples