Permutations Using Stacks

NOTE (November 11th 2014): The problem presented here was first studied by Knuth back in 1968. Several other leading experts went on to add formidable details (as basic references, there are Wiki articles on 'stack sortable permutations' and so forth). I was unaware of all that when I started on this problem and did what now can only be called very basic experimentation. But I let the article be as it was written:

-------------------------

The setup: given the ordered sequence of integers 1 to N (call this the input stream), an initially empty output stream and a stack (initially empty) which allows exactly 2 operations: {push from input, pop to output}.

Note: we cannot put anything back into the input from the stack.

Basic Question: what are the permutations of (1,2,...N) that can be generated as output with this setup?

Simple examples: if input is 1,2,3,4 one can first push 1,2, onto the stack then directly output 3, then push 4, then pop thrice from stack onto output and the overall output sequence (3,4,2,1) is generated.

Similarly, it is not hard to see that (4,1,2,3) cannot be generated as output from 1,2,3,4, whatever we do in this setup. In general: with input always 1,2,3,.. N, all N! permutations *cannot* be generated in the output. but many can be. How many?

The following recursive C function counts the permutations generateable:

--------------

double findnstackperms(int nin, int nstack)

//Note: one needs to call this function with nin as N and nstack as 0.

{

int i, j;

int ret =0;

//termination conditions

if (nstack <0 || nin <0)

ret = 0;

else if(nin ==0)

ret= 1;

else//main recursion

{

for(int i =1; i<=nin; i++)

ret += findnstackperms(nin-i, nstack+i-1);

ret += findnstackperms(nin, nstack-1);

}

return ret;

}

//--------------------

I don't know how to beat the above recursion into a closed form expression. Experiments indicate that with the first N natural numbers in the input, the number of permutations is 'only' exponential in N and so, much smaller than N!.

Update on this (Nov 10th, 2014): Thanks to Swathy Mj, I came to know that Knuth has proved that the above recursion solves to the Catalan number series.

A more serious Question:

What if m stacks are available as intermediate storage? Each stack allows 2 possible operations: { push from input, pop to output} - obviously no transfer of numbers between stacks. I have no neat recursion for this generalization, let alone a closed form answer.

----------------------

An example with more than 1 intermediate stack:

Input: numbers 1 to 10 in that order. there are 3 intermediate stacks.

Let the desired output permutation be (10,9,1,2,5,6,7,3,4,8).

Since the output sequence desired has 10 and 9 as the initial two numbers, we see:

Numbers 1 to 9 need to be pushed in some order into the 3 stacks before outputing 10 directly and then popping 9 from wherever it is onto the output.

At this point, all or some of the 3 stacks contain the numbers 1 to 8 and from the very nature of the operations, they have to be in ascending order (read from bottom to top) in each stack.

Now, 1 is the 3rd number in the output sequence so 1 should be *alone* in some stack. since 2 is the next numer needed in output, 2 should also be alone in another stack. That means one of the 3 stacks stack necessarily has the numbers 3 to 8 in ascending order from bottom to top. Fom such a state, we cannot have 5 or 6 as the next number in the output. So the specified output cannot be generated.

----------------------

We also note some facts from the other end of the 'stack count spectrum': with numbers 1 to N in input and N or N-1 stacks all permutations can be made. But with N-2 stacks, there is at least one sequence that cannot be generated. eg: input is (1 to 10) and there are 8 stacks. The permutation: (10,1,2,3,4,5,6,7,8,9) cannot be generated (not very hard to see why). So, the natural question is as number of stacks decreases from N, how fast does the number of generateable permutations decrease? When does it become exponential from factorial?

----------------------

Queues and Stacks and Dequeues: One can replace stacks with queues in the problem. It seems that the number of permutations of (1,2,...N) that can be generated with a set of m stacks appears to be the same as the number of permutations possible with m queues and the two sets or permutations are non-intersecting except for some degenerate cases. It would be interesting to see which permutations can be generated if say, 1 queue and 1 stack are allowed as intermediate stores.

Even more dramatic appears the case of dequeues as the intermediate store. It is not hard to see that a single dequeue is more powerful than 2 stacks. But it can also be seen by simple examples that a dequeue cannot generate all permutations (consider the input (1,2,3,4,5). with a single dequeue, one can't generate the permutation: (5,3,2,4,1)). Further experiments are needed.