A study of stack permutations
SUNEETA AGARWAL
Dept. of Computer Sc.& Engg.
M.N.N.I.T. Allahabad
B-21 Staff colony, M.N.N.I.T.Allahabad
INDIA
Abstract:A stack is a widely used data structure. Some of its applications are in compilers for converting an expression from infix form to prefix or postfix form, and also in recursive programming to maintain the address of returning points.In the present work we have studied the properties of those permutations which are generated using single stack.We have also derived a formula for finding the totalnumber of such permutations on a given set of elements
Key words: Stack, Push, Pop, Induction, Permutation, Expression.
1 Introduction
There are n given elements a1,a2…an.If all these elements are pushed into a stack and then popped out and kept on another side , a permutation an, an-1 ..a1 is generated. Similarly if only few out of given n elements are first pushed into the stack and a part of them are popped out and kept in the output and this process is repeated number of times till the stack becomes empty , many new permutations are thus generated. Obviously all the n! permutations on n elements are not possible to obtain this way. Therefore it becomes interesting to know how many such permutations could be generated and also to determine special structural features of these permutations.
2 Problem Formulation
Whole work is divided into following parts:
1.To determine the number of those permutations which are starting with a specific element and to construct a table of these numbers .
2.Study the special structure of the table developed above.
3.Development of a formula for the total number of permutations which are possible to generate using one stack.
3 Problem Solution
Through out the paper, let P(n,m) denote the cardinality of the set containing those permutations of a1 , a2…an each of which start with the element an-m and is obtained using one stack.Here m= 0,1,…n-1.
3.1P(n,0), P(n,1), P(n,2)
P(n,0):The only way to generate a permutation starting with an is, first push all n input elements
a1 , a2 …an into the stack and pop all one by one till the stack becomes empty.
Thus P(n,0) = 1 for all n ≥ 1.
P(n,1):To generate any such permutation a1 ,a2 .
.an-1 should be pushed, then only an-1 is popped out and put in the output. Thereafter starting with this state, different permutations for P(n,1) are possible to obtain by popping i( 0 ≤i≤ n-2) elements , then pushing the only leftover element an of the input sideand finally emptying the stack.
Thus for different values of i, following permutations are generated:
an-1an an-2…a2a1 for i=0; an-1an-2an….a2 a1 for i=1 and an-1an-2….a1an for i= n-2.
Thus P(n,1)=n-1 for n ≥1.
P(n, 2): To get such a permutation first n-2 elements a1,a2, …an-2 are to be first pushed, then an-2 is popped out and kept as output. For any permutation generated from this state exactly one of the following will be true:
an-1 precedes an or an precedes an-1.Let us put all such permutations in sets S1,S2 respectively
Thus P(n,2) = |S1| + |S2|.
3.1.1 S1:
Any permutation of S1 can be generated by popping 0 ≤ i≤ n-3 elements from the starting state, pushing an-1 and then popping out j+1 elements.Thereafter pushing an and then emptying the stack. Here
0 ≤ j ≤ n-3-i.
For i= 0 and various j=0; j=1,…j=n–3generated permutations are
an-2 an-1 an an-3….a2a1 ; an-2 an-1 an-3 an….a2a1;
an-2 an-1 an-3 an-4an….a2a1;…an-2 an-1 …….a1an.
Thus in total n-2 permutations.
For i =1 and various j =0,1….n-4 permutations are
an-2 an-3 an-1an-4 ….a2a1; an-2 an-3 an-1an-4an….a2a1;….an-2 an-3 an-1 an-4….a1an.
Thus total n-3 permutations.
Hence |S1| = (n-2) +(n-3) + …2 + 1
|S1 | = (n-2)(n-1)\2.
3.1.2S2:
Such permutations are possible as
Start from the given state pop i elements from the stack
(i =0 …n-3) , push an-1 , an and then empty the stack.
an-2 an an-1 an-3….a2a1; an-2 an-3 an an-1….a2a1… …
an-2 an-3 an-4…a1.anan-1 are the different permutations for i =0, i = 1 … i = n-3.
Thus |S2|= n-2
Hence P(n,2) = (n-2)(n-1)/2 + (n-2) = (n-2)(n+1)/2.
3.2 P(n,3),P(n,4)
Unlike P(n,0) , P(n,1) and P(n,2) , it is not simple to enumerate the ways of constructing these permutations, so to have some feeling we start with some simple cases:
3.2.1 P(n,3) when n= 4
a1 a2 a3a4; a1 a2 a4a3 ; a1 a3a2a4 ; a1 a3a4a2 ;a1 a4a3a2 are the 5 permutations.
Thus P(n, 3) = 5 when n = 4.
3.2.2 P(n,4) when n=5:
a1 a2a3a4a5; a1 a2a3a5a4; a1 a2a4a3a5; a1 a2a4a5a3; a1 a2a5a4a3; a1 a3a2a4a5 ; a1 a3a2a5a4; a1 a3a4a2a5; a1 a3a4a5a2;
a1 a3a5a4a2; a1 a4a3a2a5; a1 a4a3a5a2; a1 a4a5a3a2; a1 a5a4a3a2Thus P(5,4) = 14.
3.2.3P(n , 3) for n = 5
a2a1a3a4a5; a2a1a3a5a4; a2a1a4a3a5 ; a2a1a4a5a3; a2a1a5a4a3 ; a2a3a1a4a5; a2a3a1a5a4; a2a3a4a1a5;
a2a3a4a5a1; a2a3a5a4a1 ; a2a4a3a1a5; a2a4a3a5a1; a2a4a5a3a1; a2a5a4a3a1
Total 14 permutations.
Thus the numbers so obtained P(n , m)can be arranged in the following table
m n / 0 1 2 3 4 5 / total1
2
3
4
5
6
7
8
9
10 / 1 - - - - -
1 1 - - - -
1 2 2 - - -
1 3 5 5 5 _
1 4 9 14 14 -
1 5 14
1 6 20
1 7 27
1 8 35
1 9 44 / 1
2
5
14
42
3.3Study of Table Values
3.3.1 P(n,n-1)
Let us denote the set of all permutations on n-1 elements obtainable by single stack as T(n-1). P(n , n-1) = |T(n-1)|
Reason for it is simple : to generate any permutation of a1 , a2 …an ,starting with a1 is to start from the state where a1 is pushed and then immediately poppedwhile a2 , a3 …an-1 are stillin the input side.From this state any permutation of the set T(n-1) can be generated, So P(n,n-1)= |T(n-1)| .
3.3.2 P(n,n-1) = P(n,n-2)
Any permutation of the set P(n ,n-2) is to start from the state when a2 is on the output side, a1 is in the stack and a3 …an are still in the input side.Thus the number of permutations of the set P(n,n-2) will be same as the number of possible permutations obtained from the present state which in turn is same as the number of permutations of a1 a3 …an i.e. |T(n-1)|.
Thus P(n,n-2) = |T(n-1)| = P(n , n-1).
3.3.3P(n,r) = P(n-1 ,r ) + P(n-1 , r-1) ….P(n-1 , 0)
A permutation of P(n , r) is generated starting from the state , where an-r is on the output , a1,…an-r-1 are in the stack having an-r-1 on the top and an-r+1…an are yet on the input side.But from the present state,all those permutations on the symbols a1,… an-r-1, an-r+1…an are possible which start either from an-r-1 or an-r+1 … or an and vice versa. Thus total number of stack permutations starting with an-r
P(n , r) = P(n-1 ,r) + P(n-1 , r-1)+.. + P(n-1 , 0).
Similary one can also conclude : P(n,r) = P(n-1 , r) + P(n , r-1)
3.3.4P(n , 2) = P(n , 1) + P(n-1 , 1) + …+P(3,1)
Since P(n ,2) = P( n ,1) + ( n-1 ,2)
= P(n , 1) + P( n-1 ,1) + P(n-2 ,2)
= P( n,1) + P( n-1,1) …. P(3,1)
since P(3 ,1) = P(3,2)
3.3.5P(n ,3) = P(n, 2) + P(n-1 ,2 ) + … P( 4,2)
P(n, 3) = P( n , 2) + P( n-1 , 3)
= P(n ,2) + P( n-1 ,2) + P( n-2 , 2) +… P( 5 ,2) + P( 4,3)
= P( n , 2) + …………………………..+ P( 4,2)
since P( 4,3) = P(4,2)
3.3.6P( n,3)
P ( n, 3) = (n+1)(n-2)/2 + n(n-3)/2 + (n-1)(n-4)/2 +….5
n-3
= ∑k=1 (n-k+2)(n-k-1)/2
= (n+1)(n+2)(n-3)/6
Thus P(n ,0) =1
P(n,1) = n-1
P(n,2) = (n+1)(n-2)/2
.
.
P(n,3) = (n+1)(n+2)(n-3)/ (3.2)
3.4P(n , m)
Preposition: for all n ≥ 1 and 0 ≤ m ≤ n-1
P(n , m) =
Proof : By induction.
Basis n= 1 ; m= 0
All these are true
Hypothsis: With respect to first index, formula is true upto n0 and for any such first index value it is true when second index m is less than n0– 1
We will show that formula is also true for P(n0 , m0 + 1)
P( n0 , m0 +1) = P( n0 , m0) + P(n0 – 1 , m0 + 1) since m0 < n0 – 1 , m0 + 1 < n0 so Hypothesis can be used.
=
Hence we can say that for any n ≤ n0 if m is ≤ n-1, P(n ,m) is given by the formula.
P(n , m) =
Now we can apply induction hypothesis on first index.Let us take n = n0 + 1
Basis m= 0;
P(n0 +1 , 0) =
Hence by previous proof we can say that P(n ,m ) formula is valid for any n ≤ n0 + 1 and m ≤ n0.
Thus P(n ,m ) formula is true for any n and m as long as m ≤ n-1.
3.5Total number of stack permutations on n elements T(n) :
Since P( n+1 , n) = T(n)
4Conclusion
In this paper we have derived the properties of the permutations which are possible to obtain using single stack.This can further be extended for more than one stacks.
References:
[1] Ellis Horowitz,Fundamentals of Data Structures in C++, Galgotia Publications Pvt. Ltd, New Delhi, India, 2000.