A stack permutation of number N is defined as the number of sequences which you can print by doing the following

Keep two stacks say A and B.

Push numbers from 1 to N in reverse order in B. (so the top of B is 1 and the last element in B is N)

Do the following operations

Choose the top element from A or B and print it and delete it (pop it). This can be done on a non-empty stack only.

Move the top element from B to A (if B is non-empty)

If both stacks are empty then stop

All possible sequences obtained by doing these operations in some order are called stack permutations.

eg: N = 2

stack permutations are (1, 2) and (2, 1)

eg: N = 3

stack permutations are (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1) and (3, 2, 1)

The number of stack permutations for N numbers is C(N), where C(N) is the Nth Catalan Number.

Suppose we generate all stack permutations for a given N and then print them in lexicographical order (dictionary order), how can we determine the kth permutation, without actually generating all the permutations and then sorting them?

I want some algorithmic approaches that are programmable.

Keep two stacks say A and B.

Push numbers from 1 to N in reverse order in B. (so the top of B is 1 and the last element in B is N)

Do the following operations

Choose the top element from A or B and print it and delete it (pop it). This can be done on a non-empty stack only.

Move the top element from B to A (if B is non-empty)

If both stacks are empty then stop

All possible sequences obtained by doing these operations in some order are called stack permutations.

eg: N = 2

stack permutations are (1, 2) and (2, 1)

eg: N = 3

stack permutations are (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1) and (3, 2, 1)

The number of stack permutations for N numbers is C(N), where C(N) is the Nth Catalan Number.

Suppose we generate all stack permutations for a given N and then print them in lexicographical order (dictionary order), how can we determine the kth permutation, without actually generating all the permutations and then sorting them?

I want some algorithmic approaches that are programmable.

Topic archived. No new replies allowed.