Kth stack permutation
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.