6
$\begingroup$

Assume we have i stacks. the possible actions are:

  1. push to first stack form input
  2. pop from stack i and push it to stack i+1
  3. pop from last stack to output

If we have numbers of 1 to n starting from 1 in the input, what is the minimum value of i which can generate all permutations of 1 to n at the output?

The options are:

  1. 1
  2. 2
  3. n-1
  4. n

Option 1 obviously is not the answer, and also it's totally possible with n and n-1 stacks witch removes the option 4.

The real question is "is it possible doing with 2 stacks or we need n-1"?

$\endgroup$
5
  • $\begingroup$ Try the case $n=4$. $\endgroup$ Jun 17, 2019 at 5:08
  • $\begingroup$ The set of all numbers that are in either input or output stays the same. If you have $n$ numbers in the input initially, you will get at most $n$ numbers in the output, which is just about one permutation. How can we generate all permutations? $\endgroup$
    – John L.
    Jun 17, 2019 at 7:28
  • 3
    $\begingroup$ @Apass.Jack You want to be able to generate any permutation, not all of them at once. $\endgroup$ Jun 17, 2019 at 19:33
  • $\begingroup$ Mehdi, can you add a url or reference to the original problem? If you created this problem by yourself, can you share your motivation? $\endgroup$
    – John L.
    Jun 18, 2019 at 3:54
  • $\begingroup$ @Apass.Jack It's a question from an university entrance exam. the answers are not published yet by the officials and there is an open discussion between student's on this. i will post the answer as soon as they publish it. $\endgroup$
    – Mehdi
    Jun 18, 2019 at 4:14

1 Answer 1

7
$\begingroup$

It is not clear in the question what operations are allowed on the input and how to view or access the output. However, since we are dealing with all permutations, the answer is the same whether the input is a stack or queue and whether the output is a stack or a queue. From now on, we will assume both input and output are stacks.


What is the minimum value of $i$ which can generate all permutations of 1 to $n$ at the output?
The options are: 1) 1 $\;$ 2) 2 $\;$ 3) $n-1$ $\;$ 4) $n$

None of the given options is correct.

  • All permutations of 1 to 7 can be generated by 3 stacks.
  • The permutation 7132465 cannot be generated by 2 stacks.

The above facts can be verified by an exhaustive search by a program easily. So the minimum value of $i$ which can generate all permutations of 1 to 7 is 3. Note that $3\not=2$ and $3\not=7-1$.


Let $s_n$ be the minimum number of stacks (excluding the input stack and the output stack) which can generate all permutations of any given $n$ elements on the input stack.

It is obvious that $s_n$ is non-decreasing.

We have the following recurrence inequality of $s_n$: $$s_{2n+1} \le 1+s_n, \forall n\ge0$$ Proof: Suppose we are given $\sigma$, an arbitrary permutation of $1$ to $2n$. Here is an procedure that uses $1+s_n$ stacks to produce $\sigma$, i.e., move all numbers from $1$ to $2n$ on the input stack to the output stack so that the output stack contains $\sigma(1), \sigma(2), \cdots, \sigma(2n)$.

  1. Use the first $s_n$ stacks to move the numbers from $1$ to $n$ on the input stack to the last stack, the $s_n$-th stack so that the numbers on the last stack are in the reverse order of $\sigma$.

  2. Similarly, we are able to move the remaining numbers on the input stack, numbers from $n+1$ to $2n$ to the last stack in exactly the same way. However, we will tweak the procedure as follows.

    When a number is about to push to the last stack, we will pop out all the numbers on the last stack that should be pushed to the output stack, i.e., those numbers that appears later than that number in the sequence $\sigma(1), \sigma(2), \cdots$. Then we will push that number to the last stack. Also immediately, pop it out from the last stack to the output stack.

Now suppose we are given $\sigma'$, an arbitrary permutation of $1$ to $2n+1$. Now we will change the procedure above in the following way. Whenever we see the number $\sigma'(2n+1)$, we will move it all the way to the output stack immediately. The task remains is to move all other $2n$ numbers to the output stack as wanted, which can be done by the procedure above.

$\checkmark$

Facts:

  • $s_1=0$,
  • $s_2=1$,
  • $s_3=s_6=2$,
  • $s_7=s_{13}=3$,
  • $s_{27}\le4$,
  • $s_{55}\le5$.

Proof. The permutation $\begin{pmatrix} 123\\312\end{pmatrix}$ cannot be generated by 1 stack. $s_6=2$ can be demonstrated by a short brute-force program in Python within 1 second. The permutation $\begin{pmatrix} 1234567\\7132465\end{pmatrix}$ cannot be generated by 2 stacks. Other facts are either obvious or easily obtained, thanks to the recurrence inequality proved above.


I suspect $s_{14}=3$.

$\endgroup$
11
  • $\begingroup$ Typo, $s_3=2$ because of 312. $\endgroup$
    – John L.
    Jun 18, 2019 at 6:56
  • $\begingroup$ How do you generate $4123$ using two stacks? $\endgroup$ Jun 18, 2019 at 11:45
  • $\begingroup$ @YuvalFilmus Input stack is 1234 with 1 on the top. Output stack will be 3214 with 3 on the top, which means the permutation $1234\to4123$. Denote the state by [input stack,stack 1,stack 2,output queue]. Here are the steps. $[1234,,,]\to [234,1,,]$$\to [34,21,,]\to [4,321,,]$$\to [4,21,3,]\to [4,1,23,] $$\to [4, ,123,] \to [,4,123,]$$\to [,,4123,]\to [,,123,4]$$\to[,,23,14,]\to[,,3,214]$$\to[,,,3214]$. In words, we push 1,2,3 from input to stack 1. Then pop 3,2,1 from stack 1 to stack 2. Then we move 4 from input all the way to output stack. Then pop 1,2,3 from stack 2 to output. $\endgroup$
    – John L.
    Jun 18, 2019 at 12:28
  • 1
    $\begingroup$ In fact, $s_n\le 1+\lceil\log_2(n/3)\rceil$ if $n\not=3$. Is $s_{13}=3$ or $s_{13}=4$? $\endgroup$
    – John L.
    Jun 19, 2019 at 3:00
  • $\begingroup$ Can you explain how you achive the inequality in the last comment? $\endgroup$
    – Ahmad
    Nov 19, 2021 at 7:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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