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.. 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.
    – ithisa
    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

    if i==n 
        print res
  • Yes, that's why I first generate the n! permutations and then filter out the impossible ones.
    – ithisa
    Apr 9 '13 at 23:49
  • easier way would be to generate them directly see my edit Apr 10 '13 at 0:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.