Maximum distance within a subset of permutations

Question

I'm modelling a scheduler that accepts a sequence of requests and outputs a sequence of responses, one response per request. It can partially reorder requests, but only within a finite queue. Specifically, I have a queue with maximum size q. The numbers 1 through N are fed into the queue in order. When the queue reaches its maximum size, the scheduler removes an item from the queue and outputs it. When the end of input is reached, the scheduler removes and outputs items from the queue, one at a time. The choice of which item to remove from the queue is completely up to the scheduler. Therefore, the output is a permutation of the input, however, not all permutations are possible. For example, if the queue size is only 2, it would be impossible to output the numbers 1 through N in reverse order. I'll call the set of possible permutations P.

I have two permutations x and y that are elements of P. I want to compare them by looking at the inversion count of $xy^{-1}$. ($xy^{-1}$ is not necessarily an element of P.) What is the maximum possible value of this inversion count? Is there literature available on this topic?

Edit:

If it makes the problem any easier, Spearman's footrule could be used as the comparison instead of the inversion count. The particular choice of metric is not important as long as the distance of 21345 from the identity is less than the distance of 52341 from the identity, i.e., the distance between transposed elements is important. The triangle inequality is nice, but not absolutely necessary. (This is an engineering problem after all, so the constraints on the math are flexible.) Also, the most useful value for q at the moment is 32, although this will vary in the future.

It looks like P is not closed, which is a shame, but not surprising. Using q=2, if we let x=2143 and y=1324, then $xy^{-1}$=2413, which is not in P.

Answer 1

Let me give a very partial answer to your question, only describing what permutations lie in the set $P$: This of course depends on $q$, the size of the queue. See e.g., http://en.wikipedia.org/wiki/Permutation_pattern for the definition of avoidance used below:

• If $q=1$ then clearly $P$ just contains the identity permutation, which happens to be the set of avoiders of the classical pattern $21$.
• If $q=2$ then $P$ is the set of avoiders of the classical patterns $312$ and $321$.
• If $q=3$ then $P$ is the set of avoiders of the classical patterns $4123$, $4132$, $4213$, $4231$, $4312$, $4321$.

You can continue this description as one would expect:

• For a general $q \geq 1$, $P$ is the set of avoiders of all patterns of the form $(q+1) \pi$ where $\pi$ is any pattern of length $q$.

The justification for this is that if the size of the queue is $q$ then you can not get a large element $x$ out of the queue before $q$ smaller ones.

Answer 2

Even for q=2 it is a nice problem. In this case it is easy to show that an element of P is a concatenation of cycles like (2 ... m 1), which has inversion count (m-1). The maximal inversion count for an element of P is then (n-1), and for an element of the form xy^-1 I believe it can lie outside of P and have inversion count 2n-3.

I don't know what it will be for general q, but since each element can move at most q-1 elements forward, I suspect an upper bound like qn will apply for elements of the form xy^-1, and that P will be closed under such terms only when q=n.

I don't know any references. Any that are found I hope will be posted here.

Gerhard "Also Interested In Inversion Density" Paseman, 2013.01.17