Generate permutation using a single stack

Question

Can anyone please explain algorithm to generate the permutations possible when using only a single stack and push and pop are the only operations allowed. Have searched about it a lot, but no definite answer. Also the total number of such permutations is given by catalan numbers. But I fail to get a proof for that. Kindly explain that as well if possible.

Thanks!!

Answer 1

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

The operations are "push an item from the input queue onto the stack" and "pop an item from the stack onto the output queue".

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

             stack

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

• push 1 from input to stack
• push 2 from input to stack
• pop 2 from stack to output
• pop 1 from stack to output
• push 3 from input to stack
• pop 3 from stack to output

But you'll have a hard time if you try to generate 3 1 2.

---

How do you generate all the permutations that are possible with these operations? Well, it's trivial to do recursively: in any given state (where the "state" consists of the contents of the input queue, the stack, and the output queue), there are at most two possible operations you can perform (you can push if there is at least one item on the input queue; you can pop if there is at least one item on the stack), which will give you at most two possible new states to explore.

For further detail regarding this problem, and the relationship with Catalan numbers, go and find a copy of Knuth's "The Art of Computer Programming", volume 1 (3rd ed.) - it's discussed in §2.2.1; see exercises 2 - 5 on pp. 242-243 (and a better version of my diagram on p. 240!).

Answer 2

I was thinking about the same problem and ended up writing a small Prolog program to generate the permutations, and "discovered" the relation to Catalan numbers, and then found your question. So this is not really an answer to your question but here is the Prolog program:

% Generate permutation counts
count_pushpop(N-K) :-
    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 the n! permutations are possible:

?- 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 this would be a proof if it wasn't for the stack overflow ;)):

?- count_pushpop(N-K).
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

Answer 3

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

1. You can only read from the input sequentially.

2. Writing the output similarly occurs sequentially, and the data written to the output can not be read once written.

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

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 the Theory of Computation. I believe this is one of the exercises in chapter 4.)

Now you can easily implement an algorithm which fixes this problem by breaking any one of these assumptions. For example, if you can read from the input arbitrarily, then you don't need a stack:

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

Or if you fix a permutation, the problem becomes finite and you similarly don't need a stack. You just unfold the usual algorithm to special case over all inputs (ie just like doing partial evaluation in a compiler). This is pretty horrible, so I won't bother writing out all the details, but it still works due to the fact the total number of possible inputs is a fixed (but large!) constant.