# Generate all permutations of 1 to n with i stacks

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"?

• Try the case $n=4$. – Yuval Filmus Jun 17 '19 at 5:08
• 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? – John L. Jun 17 '19 at 7:28
• @Apass.Jack You want to be able to generate any permutation, not all of them at once. – Yuval Filmus Jun 17 '19 at 19:33
• Mehdi, can you add a url or reference to the original problem? If you created this problem by yourself, can you share your motivation? – John L. Jun 18 '19 at 3:54
• @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. – Mehdi Jun 18 '19 at 4:14

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

• Typo, $s_3=2$ because of 312. – John L. Jun 18 '19 at 6:56
• How do you generate $4123$ using two stacks? – Yuval Filmus Jun 18 '19 at 11:45
• @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. – John L. Jun 18 '19 at 12:28
• In fact, $s_n\le 1+\lceil\log_2(n/3)\rceil$ if $n\not=3$. Is $s_{13}=3$ or $s_{13}=4$? – John L. Jun 19 '19 at 3:00