6
$\begingroup$

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)?

Improve this question
$\endgroup$
6
  • $\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$ Commented Oct 25, 2017 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$ Commented Oct 25, 2017 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$ Commented Oct 25, 2017 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$ Commented Oct 25, 2017 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$ Commented Oct 27, 2017 at 11:39

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.