1
$\begingroup$

Assume a Forth-like environment with two stacks, a main one and an auxiliary one. The following operations can be done on the main stack: DUP (duplicate the top element), SWAP (swap the top two elements), DROP (drop the top value), PUSH (move the top value to the auxiliary stack) and PULL (move the top value of the auxiliary stack to the primary one).

If the main stack is organized like this (top-bottom): x <x elements> y <y elements> z <z elements>, where x, y and z are integers preceding the corresponding number of arbitrary elements, is it possible to re-arrange it like this: x <x elements> z <z elements> y <y elements> using only the operations described above?

If not, what operations can be added to satisfy this condition?

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! After the arrangement, do you mean x <x arbitrary elements> z <z arbitrary elements> y <y arbitrary elements>? $\endgroup$ – Apass.Jack Nov 4 '18 at 12:34
  • $\begingroup$ @Apass.Jack, well, the element groups should retain their values and ordering, just having their positions swapped. $\endgroup$ – Mark Nov 4 '18 at 17:39
  • $\begingroup$ Well, I think I'll need a simple explanation. Assuming the stack looks like this: 3 a b c 4 d e f g 5 h i j k l, afterwards it should be arranged like: 3 a b c 5 h i j k l 4 d e f g (the lengths are given purely for example). $\endgroup$ – Mark Nov 4 '18 at 19:46
1
$\begingroup$

You do not need more operations. In fact, you do not need DUP and DROP, either. All you need are SWAP, PUSH and PULL.

The list of states of main stack below shows how the initial state 1 a 3 p q r 2 x y is changed to 1 a 2 x y 3 p q r. The auxiliary stack is at left hand side growing to the right from its bottom at the very left. The main stack is at right hand side growing to the left from it bottom at the very right. <- means PUSHing to the auxiliary stack and -> mean PULLing from the auxiliary stack.

   <- 1 a 3 p q r 2 x y  //initial state
 1  <-  a 3 p q r 2 x y
 1 a  <-  3 p q r 2 x y
 1 a 3  <-  p q r 2 x y
 1 a 3 p  <-  q r 2 x y
 1 a 3 p q      r 2 x y  //then SWAP
 1 a 3 p q  ->  2 r x y
 1 a 3 p      q 2 r x y  //then SWAP
 1 a 3 p  ->  2 q r x y
 1 a 3      p 2 q r x y  //then SWAP
 1 a 3  ->  2 p q r x y
 1 a      3 2 p q r x y  //then SWAP
 1 a  <-  2 3 p q r x y
 1 a 2  <-  3 p q r x y
 1 a 2 3  <-  p q r x y
 1 a 2 3 p  <-  q r x y
 1 a 2 3 p q      r x y  //then SWAP
 1 a 2 3 p q  ->  x r y
 1 a 2 3 p      q x r y  //then SWAP
 1 a 2 3 p  ->  x q r y
 1 a 2 3      p x q r y  //then SWAP
 1 a 2 3  ->  x p q r y
 1 a 2      3 x p q r y  //then SWAP
 1 a 2  <-  x 3 p q r y
 1 a 2 x  <-  3 p q r y
 1 a 2 x 3  <-  p q r y
 1 a 2 x 3 p  <-  q r y
 1 a 2 x 3 p q      r y  //then SWAP
 1 a 2 x 3 p q  ->  y r
 1 a 2 x 3 p      q y r  //then SWAP
 1 a 2 x 3 p  ->  y q r
 1 a 2 x 3      p y q r  //then SWAP
 1 a 2 x 3  ->  y p q r
 1 a 2 x      3 y p q r  //then SWAP
 1 a 2 x  ->  y 3 p q r
 1 a 2  ->  x y 3 p q r
 1 a  ->  2 x y 3 p q r
 1  ->  a 2 x y 3 p q r
      1 a 2 x y 3 p q r  //final state

Once you have checked the above procedure, you will understand how to proceed in the general situations. In fact, what have been shown above is, basically, the well-known fact that if you can swap any two adjacent elements in an array, you can sort all elements in the array into any permutation you wanted.

$\endgroup$

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.