Generate substitution using a single stack

Question

Can someone explain the algorithm for generating permutations that are possible when using only one stack, and push and pop are the only operations allowed. I tried many times about this, but no definite answer. Also, the total number of such permutations is given by catalytic numbers. But I can not prove it. Please explain this if possible.

Thanks!!

Answer 1

This issue uses an input queue and an output queue, as well as a stack.

The operations "push an element from the input queue onto the stack" and "pull an element from the stack onto the output queue".

1 2 3 output ______ ______ input \ / <--+ | +--- pop | | | push | | v stack 

For example, at the input 1 2 3 you can get the output 2 1 3 with the following sequence:

• push 1 from stack entry
• push 2 from stack entry
• pop 2 from stack for output
• pop 1 from stack for output
• push 3 from stack entry
• pop 3 of stack to output

But it will be difficult for you if you try to generate 3 1 2 .

---

How do you create all the permutations that are possible with these operations? Well, it’s trivial to do it recursively: in any state (where the “state” consists of the contents of the input queue, stack and output queue), you can perform no more than two possible operations (you can click if there is at least one element in the input queue, you can pop up if there is at least one element in the stack) that will give you no more than two possible new states to study.

For more information on this issue and on the relationship with Catalan numbers, find and buy Knuth, “The Art of Programming,” Volume 1 (3rd ed.) - this is discussed in Section 2.2.1; see exercises 2 through 5 on pages 242-243 (and the best version of my diagram on page 240!).

Answer 2

Firstly, it is impossible to write an algorithm for this for arbitrary permutation under the following assumptions:

• You can only read from input sequentially.

• Writing output similarly occurs sequentially, and data written to the output cannot be read after recording.

• In addition to one stack, you are only allowed a constant amount of memory. (This means no additional recursion or data structure).

This is a consequence of the pumping lemma for context-free languages:

Wiki: http://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages

(Or also check: Michael Sipser (1997). Introduction to Computational Theory. I believe this is one of the exercises in chapter 4.)

Now you can easily implement an algorithm that fixes this problem, violating any of these assumptions. For example, if you can read from input arbitrarily, then you do not need a stack:

 def permute(seq, permutation): result = [] for i in permutation: result.push(seq[i]) return result 

Or, if you fix the permutation, the problem becomes finite, and you also don't need a stack. You simply deploy the usual algorithm to a special case for all inputs (for example, as a partial evaluation in the compiler). This is pretty terrible, so I won’t write all the details, but it still works because the total number of possible inputs is a constant (but big!) Constant.

Answer 3

I thought about the same problem and ended up writing a small Prolog program for creating permutations and “discovered” the relationship to Catalan numbers, and then found your question. So this is not the answer to your question, but here is the Prolog program:

 % Generate permutation counts count_pushpop(NK) :- length(_, N), findall(Seq, pushpop(N, Seq), Seqs), length(Seqs, K). % Create an integer sequence from 1 to N % and permutate it using all possible push-pop % operations starting with an empty stack. pushpop(N, Seq) :- numlist(1, N, List), pushpop(List, [], Seq). % Generate all the possible ways a list % of items can be pushed into a stack % and poped out of it. pushpop([], [], []). pushpop([H | List], Stack, Seq) :- pushpop(List, [H | Stack], Seq). pushpop(List, [H | Stack], [H | Seq]) :- pushpop(List, Stack, Seq). 

Proof that not all permutations of n! :

 ?- findall(Seq, pushpop(3, Seq), Seqs). Seqs = [[3, 2, 1], [2, 3, 1], [2, 1, 3], [1, 3, 2], [1, 2, 3]]. 

Proof that it generates Catalan numbers (or it would be proof if it weren't for the stack overflow;)):

 ?- count_pushpop(NK). N = K, K = 0 ; N = K, K = 1 ; N = K, K = 2 ; N = 3, K = 5 ; N = 4, K = 14 ; N = 5, K = 42 ; N = 6, K = 132 ; N = 7, K = 429 ; N = 8, K = 1430 ; N = 9, K = 4862 ; N = 10, K = 16796 ; N = 11, K = 58786 ; N = 12, K = 208012 ; ERROR: Out of global stack