2
$\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 it with 2 stacks or we need n-1" ?

$\endgroup$
  • $\begingroup$ Try the case $n=4$. $\endgroup$ – Yuval Filmus Jun 17 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$ – Apass.Jack Jun 17 at 7:28
  • 1
    $\begingroup$ @Apass.Jack You want to be able to generate any permutation, not all of them at once. $\endgroup$ – Yuval Filmus Jun 17 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$ – Apass.Jack Jun 18 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 at 4:14
1
$\begingroup$

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 are 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_i$ be the minimum value of $i$ which can generate all permutations of 1 to $n$. Then $s_1=0$, $s_2=s_3=1$, $s_4=s_5=s_6=2$, $s_7=s_8=3$.

It is not clear to me what are the value of $s_i$ for $i\ge 9$.

$\endgroup$
  • $\begingroup$ Typo, $s_3=2$ because of 312. $\endgroup$ – Apass.Jack Jun 18 at 6:56
  • $\begingroup$ How do you generate $4123$ using two stacks? $\endgroup$ – Yuval Filmus Jun 18 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$ – Apass.Jack Jun 18 at 12:28
  • $\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$ – Apass.Jack Jun 19 at 3:00

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.