TopCoder problem "RandomSort" used in SRM 402 (Division I Level One , Division II Level Three)



Problem Statement

    

You are given a int[] permutation containing a permutation of the first n positive integers (1 through n), and you want to sort them in ascending order. To do this, you will perform a series of swaps. For each swap, you consider all pairs (i, j) such that i < j and permutation[i] > permutation[j]. Among all those pairs, you choose one randomly and swap permutation[i] and permutation[j]. Each pair has the same probability of being chosen. Return the expected number of swaps needed to sort permutation in ascending order.

 

Definition

    
Class:RandomSort
Method:getExpected
Parameters:int[]
Returns:double
Method signature:double getExpected(int[] permutation)
(be sure your method is public)
    
 

Notes

-The returned value must be accurate to within a relative or absolute value of 1E-9.
 

Constraints

-permutation will contain between 1 and 8 elements, inclusive.
-permutation will contain each integer between 1 and n, inclusive, exactly once, where n is the number of elements in permutation.
 

Examples

0)
    
{1,3,2}
Returns: 1.0
Exactly one swap is needed.
1)
    
{4,3,2,1}
Returns: 4.066666666666666
In the first step, any two elements can be swapped.
2)
    
{1}
Returns: 0.0
This permutation is already sorted, so there's no need to perform any swaps.
3)
    
{2,5,1,6,3,4}
Returns: 5.666666666666666

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12174&pm=8590

Writer:

srbga

Testers:

PabloGilberto , Olexiy , ivan_metelsky , Gassa

Problem categories:

Dynamic Programming, Simple Math