retagged by
3,481 views
3 votes
3 votes

A stack A has 4 entries as following sequence a,b,c,d and stack B is empty. An entry popped out of stack A can be printed or pushed to stack B. An entry popped out of stack B can only be printed.

Then the number of possible permutations that the entries can be printed will be ?

Stack A            Stack B = empty

a(TOP)
b
c
d

                     

retagged by

1 Answer

Best answer
7 votes
7 votes
permutations which start with D:
to print D first , all a,b,c must be pushed on to stack before popping D and the only arrangement possible = D C B A
permutations start with C:
you need to push a and b from stack A to stack B , now print C
content of stack B= b a (from top to bottom)
content of stack A = d
permutations possible = 3!/2! = 3 = they are c d b a, c b d a, c b a d --> 3 permutations here
permutations starting with b :
to print b first, a will be pushed onto stack B
content of stack B= a
content of stack A= c d
you can bring these out in (3! -1) as (d a c) is not possible--> 5 possible
permutations starting with a:
fix ab
a b _ _
in this a b c d or a b dc
fix ac
a c _ _
a c b d or a c d b
fix ad
a d _ _
a d c b
total 5
total = 1+3+5+5= 14
selected by

Related questions

9 votes
9 votes
1 answer
1
Rahul Jain25 asked Oct 6, 2016
1,429 views
An item that is read as input can either be pushed to the stack and later popped and printed or printed directly. Number of print permutations that can be obtained using ...
2 votes
2 votes
4 answers
3
jaydip74 asked Jul 22, 2023
464 views
In how many ways can 3 non-negative integers be chosen such that a + b + c = 10 where a >= -1 , b >= -5 and c >= 3 ? 3666105None
0 votes
0 votes
2 answers
4
Lakshman Bhaiya asked Oct 30, 2018
1,671 views
9 different books are to be arranged on a bookshelf. 4 of these books were written by Shakespeare, 2 by Dickens, and 3 by Conrad. How many possible permutations are there...