# Permuting a list of numbers by pushing and popping onto a stack

Suppose we have some long stack of numbers. There is another intermediate stack, and a destination stack to be returned in the end. The only two operations allowed is transferring the top of the old stack to the top element of the intermediate stack and transferring the top element of the intermediate stack onto the top of the new stack. List all the possible new stacks that can be produced, assuming the original stack is used up.

I'm using Racket/Scheme. Purely functional solutions are more preferable ;)

Any ideas on how to do it? By some handwaving it seems that the following function correctly predicts whether a certain output sequence is possible, given that the input sequence is sorted from small to big:

``````(define (possible? lst)
(match lst
[(cons a b)
(and (if (andmap (λ(x) (< x a)) b) (sorted? b) #t) (possible? b))]
[x #t]))
``````

thus I can simply generate all permuations of the input list and filter out the impossible ones.

It seems that there should be a more elegant solution though, which preferably uses recursion and functional programming instead of nested loops and mutation.

-
If I'm not mistaken this would allow all possible permutations.. – Jimmy Hoffa Apr 9 '13 at 21:45
No? The possible? function would return #f for the list '(1 4 2 3). Also, try producing '(1 4 2 3) from an input of '(1 2 3 4) - it is clearly impossible without moving things from the intermediate stack back to the origin stack, which is disallowed. – user54609 Apr 9 '13 at 22:03

because you have only 2 operations are allowed you can define the sequence of operations as a strict subset of a selection of n from 2n-1 which has (2n-1)!/((n-1)!n!) possibilities (accounting that the first operation is pushing on the intermediate)

this (according to wolfram alpha) doesn't rise as fast as n! (the total amount of permutations)

this tells me that your algorithm cannot create all permutations once n becomes large enough

edit: to generate them all you can find all strings `[01]{n}` where each at any point there cannot be 1 when there is already an equal amount of 1s and 0s

``````rec(i,n,inter,res)
if i==n
print res
rec(i+1,n,inter~i,res)
if(inter.length>0)
rec(i,n,inter[0..\$-1],rec~inter[\$])
``````
-
Yes, that's why I first generate the n! permutations and then filter out the impossible ones. – user54609 Apr 9 '13 at 23:49
easier way would be to generate them directly see my edit – ratchet freak Apr 10 '13 at 0:14