PROBLEM STATEMENT
You are given a vector 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:vector
Returns:double
Method signature:double getExpected(vector permutation)
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
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)2010, TopCoder, Inc. All rights reserved.