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.