Stack

Question

How many permutations can be obtained in the output using a stack assuming that the input 1,2,3,4,5,6 such that 3 will be popped out from stack at 3rd position ?

Answer 1

Case 1:
Push 1, pop 1
push 2, pop 2
push 3, pop 3

Case 2:
push 1
Push 2, Pop 2
Pop 1
push 3, pop 3


As we can see there 2 possibilities before 3(1, 2 and 2, 1), and there will be 4 possibilities after 3  (456, 546, and 564, 654,465).
so far we got 10 sequences.
Remaining 16 will be as follows:

4 5 3 2 1 6
4 5 3 2 6 1
4 5 3 6 2 1
5 4 3 2 6 1
5 4 3 6 2 1
5 4 3 2 1 6

143256

143265

143526

143562

143652

243156

243165

243516

243561

243651

Hence, there total 26 sequences possible.

Comments

Total 16 sequences are possible

1 2 3 5 4 6

1 2 3 6 5 4

1 2 3 4 5 6

1 2 3 5 6 4

1 2 3 4 6 5

2 1 3 5 4 6

2 1 3 4 5 6

2 1 3 6 5 4

2 1 3 5 6 4

2 1 3 4 6 5

4 5 3 2 1 6

4 5 3 2 6 1

4 5 3 6 2 1

5 4 3 2 6 1

5 4 3 6 2 1

5 4 3 2 1 6

Correct me if i am wrong

---

yes you're partially correct like me. i will update my answer! why didn't you consider 123564 or 213564?

---

ok now it became 14

---

Why is it not 120 ? First three elements can be any of the 5 excluding 3 and can be chosen in 10 ways, after permutting these 3 we get 60 ways. Now the top 2 elements can be permutted in remaining 2 ways. So total number of inputs and thus the output possible 60*2 = 120.

---

it's an assumption that in this question,  given sequence of input will be followed. @xylene

---

It is given that input is 1,2,3,4,5,6 and it's not mentioned that this is the sequence.  However, if you consider that answer will be 14.

---

if sequence is not followed , then answer will be $5!=120$

---

@nikunj , @manu00x

I think these two are also a valid sequence.

123465

213465

---

@hemant yes these two are also possible.

---

@mannu00x @hemant

ok now became 16

i think there is no such procedure we should follow we have to do it manually and hence it is time consuming so i think they will not ask more then 6 (just an assumption)

if there is any pattern please let me know.

---

120 it should be i guess

---

@manu00x

there will be total of 16+10 =26

16 you have already written, 10 more with prefix(143 and 243) are

143256

143265

143526

143562

143652

243156

243165

243516

243561

243651

---

can u please tell why 120 is wrong

---

@A_I_$_h  i think you are looking this question as a permutation combination question in which 3 is fixed and 5 slots are empty and we have 5 choices to fill it hence 5!(5 factorial) but stack property should be preserved in this question

for Example:

in your 5! there must be a string 6 5 3 2 1 4 which is not possible in stack so i think your approach don't fit here

correct me if i am wrong

---

but given answer is 120

---

Manu Thakur

3 will be popped out from stack at 3rd position

 what does this mean?? 

1) third pop operation performed should be of 3

2)3 is at third position while pushing into the stack

really confused , pls help