How to implement/construct the following permutation, given two n-tuples, efficiently?
<p>I am studying queuing theory in which I am frequently presented with the following situation.</p>

<p>Let x, y both be n-tuples of nonnegative integers (depicting lengths of the n queues). In addition, x and y each have distinguished queue called their "prime queue". For example,</p>

<p>x = [3, 6, 1, 9, 5, 2] with x' = 1</p>

<p>y = [6, 1, 5, 9, 5, 5] with y' = 5</p>

<p>(In accordance with Python terminology I am counting the queues 0-5.)</p>

<p>How can I implement/construct the following permutation f on {0,1,...,5} efficiently?</p>

<ol>
<li>first set f(x') = y'. So here f(1) = 5.</li>
<li>then set f(i) = i for any i such that x[i] == y[i]. Clearly there is no need to consider the indices x' and y'. So here f(3) = 3 (both length 9) and f(4) = 4 (both length 5).</li>
<li>there are now equally sized sets of queues unpaired in x and in y. So here in x this is {0,2,5} and in y this is {0,1,2}.</li>
<li>rank these from from 1 to s, where s is the common size of the sets, by length with 1 == lowest rank == shortest queue and s == highest rank == longest queue. So here, s = 3, and in x rank(0) = 1, rank(2) = 3 and rank(5) = 2, and in y rank(0) = 1, rank(1) = 3, rank(2) = 2. If there is a tie, give the queue with the larger index the higher rank.</li>
<li>pair these s queues off by rank. So here f(0) = 0, f(2) = 1, f(5) = 2.</li>
</ol>

<p>This should give the permutation [0, 5, 1, 3, 4, 2].</p>

<p>My solution consists of tracking the indices and loops over x and y multiple times, and is terribly inefficient. (Roughly looking at n >= 1,000,000 in my application.)</p>

<p>Any help would be most appreciated.</p>
