9 votes 9 votes 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 stack, if the input sequence is $1, 2, 3, 4, 5$ in that order is __________. DS data-structures stack combinatory + – Rahul Jain25 asked Oct 6, 2016 • edited Aug 7, 2021 by soujanyareddy13 Rahul Jain25 1.5k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Habibkhan commented Oct 6, 2016 reply Follow Share Nice question ..But time taking before arriving at a conclusion. 0 votes 0 votes Rahul Jain25 commented Oct 6, 2016 reply Follow Share Yes. The only way i am knowing is by writing all permutations. I want to know if it can be solved by some logic. 0 votes 0 votes Habibkhan commented Oct 6, 2016 reply Follow Share In such questions as I said earlier you have to do what is mentioned in the question and solve accordingly.This was the confusion which I had earlier.Let me rectify 0 votes 0 votes Please log in or register to add a comment.
Best answer 10 votes 10 votes This is a problem whose soltution lies in Catalan number.In this case for any permutation no of pushes >= no of pops for any prefix of permutaion So 5th Catalan no is given by : 2nCn / (n+1) = 10C5 / 6 = 42 Hence the answer to this question should be 42. Plz refer to the link : http://math.stackexchange.com/questions/17769/using-one-stack-to-find-number-of-permutations Habibkhan answered Oct 6, 2016 • selected Nov 19, 2016 by Kapil Habibkhan comment Share Follow See all 7 Comments See all 7 7 Comments reply Rahul Jain25 commented Oct 6, 2016 reply Follow Share Answer is correct. But how do you conclude this formula.?? 0 votes 0 votes Prashant. commented Oct 6, 2016 reply Follow Share Try to do with 3 numbers . The number of permutation is equal to no. of post-order of binary search tree . since with 3 nodes number of binary search tree are 2nCn / (n+1) . 1 votes 1 votes Rahul Jain25 commented Oct 6, 2016 reply Follow Share Of course the formula is correct. But this question is fill in the blank type. Ijust want to know how such conclusion can be obtained. 0 votes 0 votes Prashant. commented Oct 6, 2016 reply Follow Share i already give you hint try with small number then you idea . 1 votes 1 votes Habibkhan commented Oct 6, 2016 reply Follow Share It is analogous to balanced parantheses problem with prefix property.Check for it u will get the idea .Only the difference is instead of opening and closing brackets , we are using push and pop here. 2 votes 2 votes Rahul Jain25 commented Oct 6, 2016 reply Follow Share Thank you guys. 0 votes 0 votes Habibkhan commented Nov 19, 2016 reply Follow Share I dont know who has downvoted my comment and for what reason..It is better to give valid argument also if one is downvoting. One does not become great by simply downvoting..If one want to show skill , then give legitimate comments ..I have no problem.. But don't do this silly thing.. 1 votes 1 votes Please log in or register to add a comment.