I came up with a problem, and I'm having trouble finding existing work on it. I'm not sure if there is a polynomial-time solution for it. Is this a well-known problem (or equivalent to one)?
We define a function
limited_sort(input, n) -> output that takes an array of comparable elements
input and an integer
n and returns
output which is a permutation of
input such that that no element in
output is more than
n spaces from its original position in
output is the permutation that has the lowest number of inversions (subsequent elements
a, b such that
a > b) out of all such permutations (if there are multiple minimal permutations,
output is the lexicographically lowest of them).
limited_sort([4, 1, 0, 2, 3], 2) returns
[0, 1, 4, 2, 3], which has 1 inversion (
4, 2). 0 inversions is not possible because you'd have to fully sort the list, and the element "4" would move 4 spaces which is not allowed.
[4, 0, 1, 2, 3] is also valid with 1 inversion but it's lexicographically higher than
[0, 1, 4, 2, 3].
Is there a solution that is polynomial-time in both
L (the length of