Как добавить определенное количество инверсий в отсортированный массив

Question

Учитывая отсортированный массив, есть ли способ вставить определенное количество инверсий (в случайных местах)? Сначала я думал, что это будет просто, но тогда осознанные инверсии могут «отменить» друг друга. Рассмотрим:

начиная с массива: 2,4,6,8
одна инверсия: 4,2,6,8

теперь, если вы хотите добавить еще одну инверсию (в случайном порядке), вы могли бы в конечном итоге с 4,2,8,6, что было бы хорошо, или вы могли бы получить 2,4,6,8, что было бы плохо, поскольку оно вернулось к оригиналу.

Он также не работает, удалив индекс после его использования. Например, 1,2,3 -> 3,2,1, если мы исключили первый и последний индекс, то мы пропустим перестановку 3,1,2, поэтому этот подход не работает.

Это не должно быть массив. Это может быть список или другая структура.

Любые предложения по изучению алгоритмов?

Answer 1

Number of inversions in an array is - 

For a given array a[n] 

    An inversion is - 
    if a[i] > a[j] such that i<j 
Also, 

    Max number of inversions = n*(n-1)/2 
    where n is the size of array 

Now use this algorithm , Inversion with count k 

    0. Sort the array in ascending order 
    1. Find greatest l, such that l(l-1)/2 < k 
    2. Take first l smallest numbers and arrange in descending order. 
    3. Compute m = k - l(l-1)/2 
    4. Place the (l+1)th smallest number and place it at (l-m + 1)th 
position, shifting others by one place to the right. 

Example : 
arr = [1,2,3,4,5] 
Inversion = 8 
l = 4 , as 4*3/2 = 6 
m = 8 - 6 = 2 

So, 

    0. Sorting the array => [1,2,3,4,5] 
    1. l = 4 
    2. 4 3 2 1 5 
    3. m = 2 
    4. Placing 5 at 3rd position, by shifting others one place to right => 4 3 5 2 1 

Hence your answer become 4 3 5 2 1