Solved
queue permutations
Posted on 2001-06-19
we are offered two queues, 'q0' and 'q1'. a collection of numbers are input into these queues. the number one is given first followed by two etc(1,2,3,..n). input sequences can be permuted in different orders by executing the queue operations q0.enq, q1.enq, q0.deq, q1.deq, in a particular order. for example, the input sequence 1,2,3, can yield five different outputs:
output control sequence
1,2,3 q0.enq,q1.enq,q0.enq,q0.deq,q1.deq,q0.deq
1,3,2 q0.enq,q0.enq,q1.enq,q0.deq,q1.deq,q0.deq
2,1,3 q0.enq,q1.enq,q1.enq,q1.deq,q0.deq,q1.deq
2,3,1 q0.enq,q1.enq,q1.enq,q1.deq,q1.deq,q0.deq
3,1,2 q0.enq,q0.enq,q1.enq,q1.deq,q0.deq,q0.deq
3,2,1 not possible
not all permutations on n integers are possible as output, as 3,2,1 shows. how would i write an algorithm that determines if the desired output sequence is possible,and if so, which sequences leads up to it. To do this, we will attach two control numbers to the sequence, one number for the enqueues and one for the dequeues. Interpret an 'qo.enq' as a '0' and 'q1.enq' as a '1', so that the sequence of enqueues becomes a string of 0's and 1's, that can be interpreted as a binary number. for example
output enq-number deq-number
1,2,3 (010)=2 (010)=2
1,3,2 (001)=1 (101)=5
2,1,3 (011)=3 (101)=5
2,3,1 (011)=3 (110)=6
3,1,2 (001)=1 (100)=4
3,2,1 not possible