4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – babou Aug 7 '14 at 16:23
  • 1
    $\begingroup$ @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. $\endgroup$ – Adwait Kumar Aug 7 '14 at 16:53
  • 1
    $\begingroup$ I'm not sure what "non-recursive" means. $\endgroup$ – Karolis Juodelė Aug 7 '14 at 17:48
  • 1
    $\begingroup$ 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. $\endgroup$ – babou Aug 8 '14 at 12:52
  • 2
    $\begingroup$ @babou Actually, that can be a good indicator of "solve my homework" -- deadline might be past. :/ $\endgroup$ – Raphael Aug 11 '14 at 15:44
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Raphael Aug 7 '14 at 19:25
3
$\begingroup$

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$.

But the initial value of $t$ is actually $min(n, m-n)$. Since it would take $\log_2 min(n, m-n)$ iterations to reach that value, starting from 1, the actual number of iterations is $1+\log_2 n - \log_2 min(n, m-n) = $1+log_2 \frac{n}{min(n, m-n)}$

Hence the total cost for this part is less than $2n+4n(1+\log_2 \frac{n}{min(n, m-n)})$

So, the overall complexity in stack moves is $O(m^2/n+n(1+\log \frac{n}{min(n, m-n))})$

In particular the complexity is linear in $n$ or $m$ when the ratio $h=m/n$ remains constant.

This is obvious for the first term $m^2/n=h^2n$.

For the second term, we have $min(n,m-n)=min(n,n(h-1))=n min(1, h-1)$. Hence $n(1+\log \frac{n}{min(n, m-n))})= n(1+\log\frac{1}{min(1, h-1))})$

$\endgroup$
1
$\begingroup$

It can certainly be done, at least in something like $O(m^2)$ steps. This is without consideration to given order of the stacks or intended result. An arbitrary element $a_i$ of either given stack can be moved to the bottom of the last stack in the following steps.

  • Given is $<a_1, \dots, a_i, \dots a_n>$; $<b_1, \dots, b_m>$; $<>$.
  • First move $b_1$ and $a_1 \dots a_{i-1}$ to last stack: $<a_i, \dots a_n>$; $<b_2, \dots, b_m>$; $<a_{i-1}, \dots, a_1, b_1>$.
  • Then move $a_1$ to second stack and move contents of last stack to first stack: $<b_1, a_1, \dots, a_{i-1}, a_{i+1}, \dots a_n>$; $<a_i, b_2, \dots, b_m>$; $<>$.
  • Finally move $a_i$ to last stack.

The resulting configuration allows for these steps to be repeated until last stack is filled in any order.

$\endgroup$
1
$\begingroup$

A simpler and more general answer

Introduction

Since we do not know for sure from the OP where is the top of the stack, I am proposing a solution that is insensitive to it, and can actually answer his question for any type of interleaving, as long as it preserve for the elements coming from a given stack the order that they had in that stack.

The general idea is quite simple: we transfer elements from A or B to C in any order corresponding to the desired interleaving. This will produce the reverse order of the desired result in C. It has a cost of exactly $m+n$ moves.

Then we are left with the problem of reversing the content of the stack C, using A and B. This is the problem I will now address.

The algorithms proposed have complexity $\Theta(m^2/n)$, which is quadratic in $m$ when $n$ is constant, and linear in $m$ when the ratio $m/n$ is constant. A simple twist in the second algorithm can double the speed.

These solutions do not require $m>n$, wich is a hypothesis of the question. It also works when $m=n$.

A somewhat more complexe version of this solution, now edited out and replaced by those given below, was initially inspired in part by the answers of ZeroUltimax and Karolis Juodelė, which are both based on the idea of moving a single element of the top of A or B to the bottom of C.

I am leaving posted my previous answer, which shows how complex a problem can become, when starting on the wrong path. Separating issues can make things much simpler.

The problem of stack reversal

We have two empty stacks A and B, respetively of size $m$ and $n$. We assume, without loss of generality, that $m\geq n$. We also have a stack C of size $m+n$. Note that there is no requirement that $m\neq n$.

Using only stack operations, and no extra memory for stack elements other than A and B, we want to reverse the order of the content of C, i.e. to end up with the same content in C in reverse order.

Notations used for the algorithms:

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

For each segment we transfer in a stack X, we call it direct if it is in its original order in C, and reverse when it is in reverse order. We comment each application of a transfer by specifying whether the transferred segment is in direct or reverse order after the transfer is performed.

A very simple stack reversal algorithm

The idea is to operate with segments of size n, taking care to inverse their order, and to inverse the order of the elements they contain.

The comments indicate the order of the elements of the segment transferred, just after tranfer. Initially all element are in C, in direct order, which we want to reverse.

Pseudocode for the simple algorithm

r = m modulo n
if r==0 then r=n
q = (m-r)/n             % not actually used; number of iterations is q+1
For i from m by -n do
  (C,A,n)      % reverse
  (A,B,n)      % direct
  (C,A,i)      % reverse
  (B,C,n)      % reverse  - final position
  if i≤n then
     (A,B,r)   % direct
     (B,C,r)   % reverse  - final position
     exit loop
  (A,C,i)      % direct
  end loop

Complexity

We measure the complexity in number of moves of one element.

Each iteration costs $3n+2i$ moves, and there is an extra $r$ moves at the last iteration.

There are $q+1$ iteration with $i=m-j\times n$ for $j\in[0,q-1]$.

So the total cost, i.e., number of moves, is:
$\begin{align*} \mathcal{C} &= r+\sum_{j=0}^q 3n+2(m-jn) \\ &= r+(q+1)(3n+2m)-2n\sum_{j=0}^qj \\ &= r+(q+1)(3n+2m)-2nq(q+1)/2 \\ &= r+(q+1)(3n+2m-nq) \\ &= r+(q+1)(3n+2m-(m-r)) \\ &= r+(q+1)(3n+m+r) \\ &= 3nq+qm+qr+3n+m+2r \\ &= 3(m-r)+qm+qr+3n+m+2r \\ &= qm+qr+4m+3n-r \\ &= qm+(q-1)r+4m+3n \\ &= m(m-r)/n + r(m-r)/n +4m+3n-r \\ &= m^2/n-mr/n + mr/n-r^2/n +4m+3n-r \\ &= m^2/n - r^2/n +4m+3n-r \\ &= m^2/n - (r^2/n+r) +4m+3n \end{align*}$

Since $r\in[1,n]$, the asymptotic complexity is $\Theta(m^2/n)$.

The algorithm is linear in $m$ when the ratio $m/n$ is constant. It is quadratic in $m$ if $n$ is constant. Note also the number of moves increases with the ratio $m/n$, in particular when $n$ gets smaller for constant $m$, and the algorithm no longer works for $n=0$.

The coefficient of the main term is $1/n$ when the algorithm is quadratic because $n$ is constant.

The result is of course the same for the initial interleaving problem, as it take only a linear amount of extra moves.


An stack reversal algorithm that is twice as fast

The analysis of the previous algorithm shows there seem to be no way of escaping the back and forth transfer of the bulk of the stack. But the algorithm would be faster if we could do more work, whenever the stack is thus moved between C and A. The limiting factor is the size $n$ of the smaller stack B, which is the maximum that may be moved together from one end of the stack content to the other end. But the weakness of the previous algorithm is that it works on only one end, building the final reversed stack at the bottom of C. We now propose to use the same strategy, but working on both end at the same time, building the lower half of the final reversed stack at the bottom of C and the upper half in direct order at the bottom of A. This allows to process $2n$ elements for each back and forth movement of the stack, and will thus double the speed, at least when $m/n$ is large, which is precisely what makes the algorithm otherwise slower.

The stacks C and A have then a symmetrical role for most of the algorithm.

The faster algorithm in pseudocode

s = m+n modulo 2n
if s==0 then s=2n
t = (m+n-s)/2n        % number of iterations, not actually used
For i from m by -2n while i>n do
  (C,A,n)      % reverse
  (A,B,n)      % direct
  (C,A,i)      % reverse
  (B,C,n)      % reverse  - final position in C
  (A,B,n)      % direct
  (A,C,i-n)    % direct
  (B,C,n)      % reverse
  (C,A,n)      % direct   - final position in A
  end loop
if s≥n then
  (C,A,n)      % reverse
  (A,B,n)      % direct
  (C,A,s-n)    % reverse
  (B,C,n)      % reverse  - final position in C
  (A,B,s-n)    % direct
  (B,C,s-n)    % reverse  - final position in C
else
  (C,A,s)      % reverse
  (A,B,s)      % direct
  (B,C,s)      % reverse  - final position in C
  end if
(A,C,t*n)    % reverse  - push back into C the part of the work accumulated in A

Complexity The cost of one iteration is $5n+2i$ where $i=m-2nj$ for $j\in[0,t-1]$

So the cost of the loop is
$\begin{align*} \mathcal{C}_{loop} &= \sum_{i=0}^{t-1} 5n+2(m-2nj) \\ &= t(2m+5n) -4n(t(t-1)/2)) \\ &= t(2m+5n-2n(t-1)) \\ &= t(2m+7n-2nt) \end{align*}$

Since $2nt=(m+n-s)$ we have
$\begin{align*} \mathcal{C}_{loop} &= t(2m+7n-(m+n-s) \\ &= t(m+6n+s) \end{align*}$

The cost of the conditional is $\mathcal{C}_{if}$ = $3s$ in both branches

And the final transfer of about half the stack from A to C costs $nt$, since there were $t$ iteration storing $n$ element each in A.

So the total cost is
$\begin{align*} \mathcal{C} &= t(m+6n+s)+3s+nt \\ &= t(m+s)+3s+7nt \\ &= t(m+s)+3s+7(m+n-s)/2 \\ &= t(m+s)+(7m+7n-s)/2 \\ &= tm+(t-1/2)s+7(m+n)/2 \\ &= m(m+n-s)/2n + ((m+n-s)/2n-1/2)s +7(m+n)/2 \\ &= m^2/2n+m/2+ms/2n + ms/2n+s/2-s^2/2n-s/2 +7m/2+7n/2 \\ &= m^2/2n+4m +ms/n - s^2/2n +7n/2 \\ &= m^2/2n+ (4+s/n)m - s^2/2n +7n/2 \end{align*}$

Since $r\in[1,2n]$, the asymptotic complexity is $\Theta(m^2/n)$.

The algorithm is linear in $m$ when the ratio $m/n$ is constant. It is quadratic in $m$ if $n$ is constant. Note also the number of moves increases with the ratio $m/n$, in particular when $n$ gets smaller for constant $m$, and the algorithm no longer works for $n=0$.

Comparison with the simpler algorithm

Note however that the term of the cost that determine this complexity when quadratic, which is the worse situation, is $m^2/2n$. It coefficient $1/2n$ is half the coefficient for the previous algorithm, so that this algorithm is asymptotically faster than the previous one by 50% when it is quadratic.

The result is of course the same for the initial interleaving problem, as it take only a linear amount of extra moves, actually $m+n$ moves.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.