A program attempts to generate as many permutations as possible of the string,…
2004
A program attempts to generate as many permutations as possible of the string, 'abcd' by pushing the characters a, b, c, d in the same order onto a stack, but it may pop off the top character at any time. Which one of the following strings CANNOT be generated using this program?
- A.
abcd
- B.
dcba
- C.
cbad
- D.
cabd
Attempted by 748 students.
Show answer & explanation
Correct answer: D
Answer: cabd cannot be generated.
Reasoning: To output the character 'c' first we must have pushed a, b, c and then popped c. After popping c the stack still contains a and b, with b on top of a. Because b is above a on the stack, b must be popped before a. Therefore it is impossible for 'a' to appear before 'b' after 'c' in the output. The sequence cabd requires 'a' before 'b' after 'c', so it cannot be produced by this push/pop process.
To produce abcd: push a, pop a; push b, pop b; push c, pop c; push d, pop d.
To produce dcba: push a, push b, push c, push d; then pop d, pop c, pop b, pop a.
To produce cbad: push a, push b, push c, pop c (outputs c), pop b (outputs b), pop a (outputs a); then push d, pop d (outputs d).
Conclusion: cabd is not achievable because after producing c the stack order forces b to appear before a.