Invalid sequence in stack permutation

[crazyboy]

Invalid sequence in stack permutation ????

inpurt sequence ... 1 2 3 4 5

1) 4 3 5 2 1
2) 2 3 5 4 1
3) 5 4 3 2 1
4) 3 4 1 5 2

Answer is .... 4) ..... but i dont know how ?

can any one explain me ? ? ?
please ... thnks ...

[arkoenig]

What is the question?

[crazyboy]

question is ... find invalid sequence in stack permutation when input is 1 2 3 4 5 ..

option are given as above ...

[arkoenig]

OK... What do you know about stack permutations?

[crazyboy]

i know abt permutation ... i dont know about stack permutation ...

[arkoenig]

I guess that would be a good place to start, then. Because if you don't know what a stack permutation is, and someone else answers the question for you, you aren't doing your own homework.

[crazyboy]

i come to know that ... using three stack ... stack permutation is performed ...
pop from first stack and push in second ...
pop from second and push in third ...
backward move not possible ... third stack gives permutation sequences ..

am i right ????

[arkoenig]

OK, now see whether you can figure out how to use these stacks to achieve each of the permutations in the exercise. I suggest you start with (3) because it's the easiest.

[crazyboy]

ok ...
i have done with 3 stacks and i got answer.
according to me 2nd option is also rong ... am i right ? ? ?

[arkoenig]

Can you prove it? Or did you just look for a solution for a while and then give up?

[crazyboy]

tell me first one thing ... stack permutation performed only with 3 stacks or ... it may be any number of stack ... ? ? ? ? ?

[arkoenig]

It's your course.

[bamasohn]

we can have a permutation as - 1,3,5,4,2 which is generated by the following sequence of operations -

      Operation         Stack                 Output

1.    print()             -                     1
2.    push(2)             2                     1   
3.    print()             2                     1,3
4.    push(4)             2,4                   1,3
5.    print()             2,4                   1,3,5
6.    pop()               2                     1,3,5,4
7.    pop()               -                     1,3,5,4,2