Return to 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.

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.

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}$. (I don't know if $xy^{-1}$ is 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.

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.

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}$. (I don't know if $xy^{-1}$ is an element of P.) What is the maximum possible value of this inversion count? Is there literature available on this topic?

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}$. (I don't know if $xy^{-1}$ is 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.