TopCoder Statistics - Problem Statement

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

{1,3,2}

Returns: 1.0

Exactly one swap is needed.
{4,3,2,1}

Returns: 4.066666666666666

In the first step, any two elements can be swapped.
{1}

Returns: 0.0

This permutation is already sorted, so there's no need to perform any swaps.
{2,5,1,6,3,4}

Returns: 5.666666666666666
{1,2}

Returns: 0.0
{2,1}

Returns: 1.0
{1,2,3}

Returns: 0.0
{2,1,3}

Returns: 1.0
{2,3,1}

Returns: 2.0
{3,1,2}

Returns: 2.0
{3,2,1}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Returns: 13.221053196152711

Maximal number of inversions.
{8,7,6,5,1,4,3,2}

Returns: 12.895467847303319

Almost maximal number of inversions.
{4, 1, 2, 3}

Returns: 3.0

3 inversions; 1, 1, or 1 inversion removed.
{1, 4, 3, 2}

Returns: 2.333333333333333

3 inversions; 3, 1, or 1 inversion removed.
{2, 1, 4, 3, 6, 5, 8, 7}

Returns: 4.0

Maximal number of pairwise independent inversions.
{4, 3, 2, 1, 8, 7, 6, 5}

Returns: 8.133333333333333

Two independent 10-inversion groups.
{5, 4, 3, 2, 1, 8, 7, 6}

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

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

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

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

Returns: 0.0

Longest test with no inversions.
{8, 7, 6, 5, 4, 3, 2, 1 }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Returns: 8.333333333333332

Statistics

Problem Statement for "RandomSort"

Problem Statement

Definition

Notes

Constraints

Examples