The number of permutations is n ! (factorial n). However, it is very difficult to find all permutations for large n.

Thank you for your response sir. You are correct that number of permutations will be n! but all of them can not be a permutation coming out of the stack.

Like 4123 can not be which surely comes in n! permutations.(n=4 in this case)

if we put 1234 in the stack and first take out 4, we cant take out 1 immediately because we have 3 and 2 already pushed in the stack. I am asking about the formula to get the number of permutations which are possible in stack operation..

Can you please define the question more clearly? If you have a given permutation in a stack and can only remove from one end, then there are no choices involved.

While it may be interesting to generate all permutations, it may be confusing to generate them on some unknown constraint. In general it is n! but if you have some hidden constraint it is hard to guess the real calculation.

If stack is your constraint, I am sorry to inform you that there is no relationship between permutations and stacks.

That is because you can push anything on a stack regardless of whether it is a duplicate or not while for permutations you surely wouldn't want duplicates. Therefore, the number of elements of any permutation shouldn't be influenced by whether they are on a stack or some other data structure.

Did you check Knuth's Art of Computer programming on that?

Suppose 1 2 3 and 4 are to be pushed onto the stack. Then the permutation can take place like this-

push 1 onto the stack

push 2 onto the stack

pop out 2 out of the stack (2)

push 3 onto the stack

push 4 onto the stack

pop out 4 out of the stack (4)

pop out 3 out of the stack (3)

pop out 1 out of the stack (1)

So the original order of 1 2 3 4 has been changed to 2 4 3 1.

This is just one example of possible permutations. My question is for a given n (n=4 in the example) how many different permutations are possible??

It is not only 1 permutation for sure. You don't have to push all the elements at once in order to get the possible permutation. But for example, you can push 3 only after pushing 1 and 2 because they are put in that order 1 2 3 4. You can pop out 2 before pushing 3 and 4 for example.

I hope it is clear now.

Yes I checked Knuth's Art of computer programming but i cant understand anything from the given explanation.

Claim: 2^{n-1} different permutations that can be obtained by a stack.

Proof. Suppose n numbers are to be pushed onto the stack with the order 1 -> 2 -> ... -> n.

Upper Bound:

For each 1 "members of {1,2,..., n-1} - S in descending order", where S is a subset of {1,2, ..., n-1} such that i is a member of S if and only if "pop()" is executed right after "push(i)". Let call such a permutation P_S. Then, It is obvious that P_S' != P_S if S' != S. Therefore, at least 2^{n-1} different permutations that can be obtained by a stack.

Q.E.D.

Do I correctly understand your question?

Thank you so much for your effort. But there is some problem.

If you take the example of 3 elements 1 2 3. Possible permutations = (3 2 1), (1 2 3), (2 1 3), (1 3 2) and (2 3 1). The number of possible permutations are 5.

According to your proof if n=3, Total number of possible permutations are -

2^{3-1} = 2^2 = 4.

This is a very interesting problem, thanks for the clarification. However, I don't think there is a "nice" answer. We can model this with a two-parameter recurrence relation, T(i,j) where i is the number of elements that have yet to be pushed on the stack and j is the number of elements currently on the stack. The answer to your question would then be T(n,0) for a given value of n. Your choices are pushing or popping if i>0 or j>0, respectively so this is:

T(i,j) = 1 if j>1 and i=0 (i.e. a permutation)

T(i-1,j+1) if j=0 and i>0 (i.e. only push)

T(i-1,j+1) + T(i,j-1) otherwise (i.e. can push or pop)

I tried but couldn't come up with a nice recurrence that only depends on values of T(i,0). If you expand this you get T(i,0) = T(i-3,3) + 2T(i-2,1), (assuming i > 3 of course). Since your first option is always to push the first element, T(i-2,1) = T(i-1,0) so we have that T(i,0) = T(i-3,3) + 2T(i-1,0). Unfortunately, the T(i-3,3) part seems to depend on many of the previous values. I kept finding possible relations that would fail on the next value of n (I gave up after 6).

So, this problem appears to be of the kind that is best answered with exhaustive search and as it is now well characterised, it should also be fairly easy for experts here to code an algorithm to rigorously explore the solution space.

@Chris: Can you provide a suitable pseudocode for your approach?

@William: Yes. If you really want all of the permutations then you might as well just put the numbers from 1 to n into a queue and then recurse repeatedly on the option to either put an element from the queue in the stack or pop an element from the stack (if the queue or stack are nonempty, respectively). However, we can do some nice dynamic programming to get the number of permutations quickly.

If we create an n x n table of values T[i][j] then we can find T(n,0) in quadratic time (O(n^2)) . Note that we can only fill in the upper left triangle of the table.

for j in 1 to n

T[0][j] = 1

for i in 2 to n

T[i][0] = T[i-1][1]

for j in 1 to (n - i)

T[i][j] = T[i-1][j+1] + T[i][j-1]

return T[n][0]

You can think of this as filling the table row by row left to right. Each entry is the sum of the element to its immediate left (T[i][j-1]) and diagonal upper-right (T[i-1][j+1]). The very first row is all 1's and the first column only depends on the upper-right value.

Hmm, research gate killed my formatting. Lets try this:

1 for j in 1 to n; do

2 T[0][j] = 1

3 done

3 for i in 2 to n; do

4 T[i][0] = T[i-1][1]

5 for j in 1 to (n - i); do

6 T[i][j] = T[i-1][j+1] + T[i][j-1]

7 done

8 done

9 return T[n][0]

Sorry for all of the posts. That one has a couple of bugs (I repeated 3, although the line numbers did not allow proper indenting as I had hoped and the fourth line should start i at 1. I've also attached a perl script I wrote to test this.

1 for j in 1 to n; do

2 T[0][j] = 1

3 done

4 for i in 1 to n; do

5 T[i][0] = T[i-1][1]

6 for j in 1 to (n - i); do

7 T[i][j] = T[i-1][j+1] + T[i][j-1]

8 done

9 done

10 return T[n][0]

Example for n=6:

1 1 1 1 1 1

1 2 3 4 5 6

2 5 9 14 20

5 14 28 48

14 42 90

42 132

132

@Chris: Thanks for the algorithm pseudocode. I can now more thoroughly see how you solve the problem.

Might I also interest you in my analysis of genome disorder? See my contribution Characters and Derivation of the Maximally Disordered Genome. I am looking for high-quality critiques of the presented data, with an eye to analyses that address the given sequences in terms of Shannon's model of communication channel behavior.

LOL, I should have recognized those. These are the catalan numbers so the formula is (2n)!/(n!(n+1)!) .

EDIT:

Here is a relevant paper: http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/112

You can apparently get all 312-avoiding permutations in this manner. Also, Patrick had the best suggestion as this is in vol 3 of the Art of Computer Programming.

Yes... these are catalan numbers.... :) Thanks to all

@Chris

Can't we better represent it by this matrix -

1 1 1 1 1 1

2 3 4 5 6

5 9 14 20

14 28 48

42 90

132

And the diagonal elements are our series .

The answer is the nth Catalan number. It is equal to C(n) = (1/(n+1))*((2n)Cn)