Given a sorted array, is there a way to insert a specific number of inversions (at random locations)? At first I thought this would be straightforward, but then realized inversions can "undo" each other. Consider:
starting with array: 2,4,6,8
one inversion: 4,2,6,8
now if you wanted to add another inversion (at random) you could end up with 4,2,8,6 which would be good or you could end up with 2,4,6,8 which would be bad as it is back to the original.
It also doesn't work removing an index after it has been used. For example 1,2,3 -> 3,2,1 if we excluded the first and last index then we miss out on the permutation 3,1,2 so this approach doesn't work.
It doesn't have to be an array. It could be a list or other structure.
Any suggestions on algorithms to look into?