answer is right there in the strings: S = PPXXPXPXPPX... Possible permutations = No. of ways to generate strings of P/X's such that in each sub-string S[0..i] no. of P's is always greater than or equal to no. of X's. You can also view this as - all possible strings of n balanced parentheses. This turns out to be nothing but famous Catalan number = 1/(n+1) * 2nCn Heres' wikipedia link to a formal proof<http://en.wikipedia.org/wiki/Catalan_number#Fifth_proof> .
In case if you have duplicates you can discard the repitions easily after calculating Cn. On 21 October 2012 14:29, Shruti <fundooshr...@gmail.com> wrote: > we can generate permutations using stack. For example, if n=1,2,3 and > Push() is denoted by "P", and Pop() by "X", > then we can generate permutations as : > PPPXXX = 321 > PPXXPX = 213 > PXPXPX = 123 > PXPPXX = 132 > PPXPXX = 231 > > (note : at any point, #P's>=#X's and finally, #P's=#X's) > > ques :- Given n elements, find the number of permutations which are > possible and which are not possible?? > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/8ZitrJFT4zUJ. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
