TopCoder problem "RandomShuffle" used in TCHS SRM 47 (Division I Level Three)



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

0)
    
{1}
Returns: 1.0
1)
    
{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,3,2}
Returns: 0.1851851851851852
3)
    
{4,2,5,1,3}
Returns: 0.006720000000000001
4)
    
{4,6,9,3,5,8,10,1,7,2}
Returns: 2.825E-7

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7833

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10803&pm=7833

Writer:

stone

Testers:

PabloGilberto , brett1479 , Olexiy , ivan_metelsky

Problem categories:

Brute Force, Search