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 input. 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).

For example, 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 n and L (the length of input)?

  • $\begingroup$ Welcome to CS.SE! Are you asking for something that's polynomial in the length of the array, or polynomial in $n$, or both? There might be algorithms that are exponential in $n$ but polynomial in the length of the array (for instance). What's the context in which you encountered this problem? $\endgroup$ – D.W. Oct 25 '17 at 4:53
  • $\begingroup$ Polynomial in both. The brute-force solution would be something like Theta((2 * n + 1) ^ L) (where L is the length of input). That's polynomial in n but not in L. $\endgroup$ – Kerrick Staley Oct 25 '17 at 18:08
  • $\begingroup$ I encountered this problem at work. We have input records that have server and client timestamps associated with them. In general you want to process them in order of client timestamp because records can be delivered out-of-order to the server. But sometimes the client timestamps are very wrong. So you want to start with the server order and then try to sort by the client timestamp as best as possible without reordering too much. $\endgroup$ – Kerrick Staley Oct 25 '17 at 18:14
  • $\begingroup$ Dynamic programming could give you an algorithm of time $n^{O(n)}L$. Better, but still not what you want. Btw, I don't think $n^L$ is polynomial in $n$, because $L>n$ in your question. Interestingly, $2^{\log n\log L}$ is polynomial in $n$ for every given $L$ and vice versa, but it cannot be bounded by any polynomial in $n$ and $L$. $\endgroup$ – Willard Zhan Oct 25 '17 at 21:11
  • $\begingroup$ I suppose part of the problem is limited_sort not being a function. E.g.limited_sort([3,2,1], 1) = [2,3,1]; [3,1,2]. $\endgroup$ – reinierpost Oct 27 '17 at 11:39

I think absolutely minimising the number of inversions makes this very hard. If you just say "I want an array that is a bit better sorted, without moving any item by more than n positions": Fill a heap with the first n+1 array elements. Then remove the smallest element in the heap and put it into the first array position, unless there is an array element in the heap that would end up moving too far. Add the next array element to the heap and repeat. Obviously stop adding elements to the heap when you run out of elements.

This will find [0, 1, 4, 2, 3] in your example.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.