Interleaving algorithm for 2 stacks

Suppose I have two stacks $<a_1,a_2,...a_m>$ and $<b_1, b_2,...b_n>$ and a third stack of size $m+n$. I want to have the third stack in the following manner, $$<a_1,b_1,a_2,b_2,...a_n,b_n...a_m-1,a_m>$$ for $$m>n$$ This was easy to do if the two initial stacks were not size constrained. But if the two stacks are size constrained, I am in a fix.

Is it even possible to interleave the elements of the two stacks into a third stack in constant space? Also what would be the minimum number of moves to do this? I know using recursion this can be reduced to Tower of Hanoi variant, but what about a non-recursive algorithm?

• A bit of context would help. Were do these stacks come from. Do you intend to repeat the operation with stacks thus obtained. Why is it easy when stacks are not size constrained (just to understand what is the problem). – babou Aug 7 '14 at 16:23
• @babou, if the stacks were not size contained all I had to do was pop an element from the first stack, then from the second and push it into the third, continue till both stacks are empty. Then simply pop out all elements and push all of them into any of the two empty stacks and I have the answer. – Adwait Kumar Aug 7 '14 at 16:53
• I'm not sure what "non-recursive" means. – Karolis Juodelė Aug 7 '14 at 17:48
• Can you confirm that, as one should infer from your previous comment, the top of the stack is on the left, the small index side? As it stands, your question is not precise enough. – babou Aug 8 '14 at 12:52
• @babou Actually, that can be a good indicator of "solve my homework" -- deadline might be past. :/ – Raphael Aug 11 '14 at 15:44

Here's an algorithm that works without using recursion. I might say it's even easier to do without recursion.

I'll be working off the underlying assumption that you don't have access to temporary variables, and that the only available operation to you is $pop(s, d)$ which pop the top element of s(source) and places it on top of d(destination). E.g.: we have the stacks $A=<a_1,a_2,a_3>$ and $B=<>$. After calling $pop(A,B)$ we have $A=<a_1,a_2>$ and $B=<a_3>$.

First, I'll define a new function $popm(s,d,c)$. It's role is to iterate $pop(s,d)$ c times. E.g.: $A=<a_1,a_2,a_3>$ and $B=<>$. After calling $popm(A,B,3)$, $A=<>$ and $B=<a_3,a_2,a_>$.

Here is the proposed algorithm.

1. Start with $A=<a_1,a_2,\dots,a_m>$, $B=<b_1,b_2,\dots,b_n>$ and $C=<>$
2. $pop(B,C,n)$. $A=<a_1,a_2,\dots,a_m>$, $B=<b_1,b_2,\dots,b_n-1>$ and $C=<b_n>$ The goal is free a spot in $B$
3. $popm(A,C,m)$. $A=<>$, $B=<b_1,\dots,b_n-1>$ and $C=<b_n,a_m,\dots,a_2,a_1>$ You've exposed $a_1$ on top of $C$
4. $pop(C,B)$. $A=<>$, $B=<b_1,\dots,b_n-1,a_1>$ and $C=<b_n,a_m,\dots,a_2>$ Have $B$ hold the value $a_1$ on top
5. $popm(C,A,m-1)$. $A=<a_2,a_3,\dots,a_m>$, $B=<b_1,\dots,b_n-1,a_1>$ and $C=<b_n>$ Restore $A$ (excluding $a_1$) to it's original order. Also, have $A$ hold $b_n$ for now.
6. $pop(C,A)$. $A=<a_2,a_3,\dots,a_m,b_n>$, $B=<b_1,\dots,b_n-1,a_1>$and $C=<>$ Have $A$ hold $b_n$ for now.
7. $pop(B,C)$. $A=<a_2,a_3,\dots,a_m,b_n>$, $B=<b_1,\dots,b_n-1>$ and $C=<a_1>$ Put $a_1$ at the bottom of $C$, it's desired place.
8. $pop(A,B)$. $A=<a_2,a_3,\dots,a_m>$, $B=<b_1,\dots,b_n-1,b_n>$ and $C=<a_1>$. Restore $b_n$ to the top of B
9. Interchange $A$ and $B$ and repeat from step 1, adjusting for the new state of $A$, $B$ and $C$. You can ignore steps 2, 6 and 8 since you now will have a free spot on top of B from now on.
10. When $B$ has been emptied, $popm(A,B,m-n)$ then $popm(B,C,m-n)$ to have your remaining stack $A$ do a "double back flip" off $B$ onto $C$.

Let me say why this isn't related to tower of Hanoi. In the Hanoi problem, you cannot inverse the tower. Moreover, you have the middle peg as a temporary holder, which we don't have. Finally, in this example, you can reverse the order on the elements.

• I think your answer can be made much more readable by a) using code markdown and b) separating (pseudo)code from idea and correctness arguments. – Raphael Aug 7 '14 at 19:25

Note: I found a better technique which I give in a separate answer, which is more general, faster and simpler, though the complexity results remain somewhat similar. I chose to leave this answer rather than replace it, as it may be interesting to compare, and both solutions were too long for a single answer.

Let A, B and C be the three stacks. I assume that the top of A and B are on the small index side.

I note (X,Y,p) the transfer of p elements from the top of X to the top of Y. This has of course the effect of inverting the order of these p elements, and has a cost p.

Let q and r the quotient and remainder of the integer division of m by n. Thus m=q*n+r.

Pseudocode for the interleaving

% transfer of the m-n unmatched tail by chunk of n elements
For i from 1 by 1 to q-1 do
% transfer the bottom n elements remaining in A
(B,C,n)
(A,C,m-i*n)
(A,B,n)      % bottom n
(C,A,m-i*n)
(B,C,n)      % bottom n
(C,A,n)      % bottom n
(C,B,n)
(A,C,n)      % bottom n
end loop
if r≠0 then
% transfer the remaining r elements of the umatched tail
(B,C,n)
(A,C,n)
(A,B,r)      % bottom r
(C,A,n)
(B,C,r)      % bottom r
(C,A,r)      % bottom r
(C,B,n)
(A,C,r)      % bottom r
end if

% Now we have transferred the extra elements of A at the bottom of C.
% We have only 2n slots available in C, for intertwining A and B.
% But we have m-n free slots in A.

(A,C,n)   % rest of A inverted in C
(B,A,n)   % B inverted in A
k=n       % number of remaining elements of each stack still to be transferred
t=m-k     % available space in A to do the transfer
while k>0 do
t=min(k,t)
(C,A,t)   % last t of A in direct order in A
(C,B,k-t) % top rest of A in B in direct order
(A,B,t)   % last t of A inverted in B
For i from 1 by 1 to t do    % intertwin in C last t elements of remainder
(A,C,1)
(B,C,1)
end loop
(B,C,k-t) % top rest of A inverted in C
k=k-t
t=2t
end  loop

Complexity

I am only counting the number of moves. It actually gives the complexity since the control statements introduce only a constant factor on the moves and the number of moves is polynomial.

For one iteration of the first loop : $6n+2(m-i\times n)$

Hence the cost of the loop is $\sum_{i=1}^{q-1}6n+2(m-i\times n)$ = $(q-1)(6n+2m)-2nq(q-1)/2$ = $(q-1)(6n+2m-nq)$ = $(q-1)(6n+2m-(m-r))$ = $(q-1)(6n+m+r)$

The cost of the following conditional is at worst $4(n+r)$

So the total cost for the last $m-n$ elements of stack A is majored by $q(6n+m+r) \leq q(7n+mn/n) \leq 7m+m^2/n$

The cost of transferring the tail of A is quadratic in $m$ when $n$ is constant, as B becomes too small with increasing values of $m$ to do the tranfer in a fixed number of passes over the whole stack. The linear decrease of the remaining part to be transferred does not help enough.

Things are however better with the parts of the two stacks that must be intertwined.

There is a first cost of $2n$.

The cost of one iteration of the loop is $2t+2(k-t)+2t$, the cost of the inner loop being $2t$. So this makes a total of $2(k+t)$.

If $m\geq 2n$ then the loop is executed only once, with $k=t=n$, hence the cost is $4n$. Note that $4n\leq 2m$ in this case.

Otherwise we start the loop with $k=n$ and $t=m-n$, so that we have $k+t=m$. But the update k=k-t; t=2t at the end of the loop preserve this property as an invariant. So each iteration actually costs $2(k+t)=2m$, except possibly the last one, since $t$ may be reduced by the statement t=min(k,t), thus lowering the cost of that last iteration. Note that, in this case, $2m\leq 4n$.

Since $t$ doubles at each iteration, but will not be greater than $n$, the number of iterations is at worse $1+\log_2 n$, when $t$ starts with value 1. Note that there must be at least one iteration when $n=1$ (though it could be simplified), in which case $\log_2 n=0$.