RandomSort | Topcoder Archive

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
```

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)2024, Topcoder, Inc. All rights reserved.