14 7 s 128 MB
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.
The first line contains the number of test cases T (T ≤ 200).
For each test case, space-separated two integers n - number of elements in permutation - and n integers as permutation given on the first line.
- 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.
4 3 1 3 2 4 4 3 2 1 1 1 6 2 5 1 6 3 4
1.00000 4.06667 0.00000 5.66667