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.
2
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[$])
2