Problem in Understanding Algorithm from TAOCP "Multiply Permutations in Cycle Form"

Question

I am not able to understand one algorithm discussed in TAOCP Volume 1; Section 1.3.3 named as "Algorithm A" stated as "Multiply permutations in cycle form" while compared with the stated example in next page.

The step that is not clear is mentioned in 8th and 9th rows;i.e. how can be the "CURRENT" value becomes "g" after the previous iteration where the CURRENT value was "d"?

Please refer to "The Art of Computer Programming Volume 1" by Knuth for more details (section 1.3.3). It contains the detailed description of this algorithm.

Detailed Algorithm:

Algorithm A (Multiply permutations in cycle form).

This algorithm takes a product of cycles, such as (6), and computes the resulting permutation in the form of a product of disjoint cycles. For simplicity, the removal of singleton cycles is not described here; that would be a fairly simple extension of the algorithm. As this algorithm is performed, we successively "tag" the elements of the input formula; that is, we mark somehow those symbols of the input formula that have been processed.

• A1. [First pass.] Tag all left parentheses, and replace each right parenthesis by a tagged copy of the element that follows its matching left parenthesis. (See the example in Table 1.)
• A2. [Open.] Searching from left to right, find the first untagged element of the input. (If all elements are tagged, the algorithm terminates.) Set START equal to it; output a left parenthesis; output the element; and tag it.
• A3. [See CURRENT.] Set CURRENT equal to the next element of the formula.
• A4. [Scan formula.] Proceed to the right until either reaching the end of the formula, or finding an element equal to CURRENT; in the latter case, tag it and go back to step A3.
• A5. [CURRENT = START?] If CURRENT i- START, output CURRENT and go back to step A4 starting again at the left of the formula (thereby continuing the development of a cycle in the output).
• A6. [Close.] (A complete cycle in the output has been found.) Output a right parenthesis, and go back to step A2.

Answer 1

In my copy of the book, Row #7 has CURRENT value d, Row #8 has CURRENT value g, and Row #9 has CURRENT value a. I'll therefore assume you are confused about the transition between Rows #7 and #8, which are as follows:

Row #  After step no.  START  CURRENT  ( a c f g a ( b c d b ( a e d a ( f a d e f ( b g f a e b  Output
  #7        A5           a       d     x x       x x   x   x x     x x x   x     x x           x    d
  #8        A5           a       g     x x       x x   x x x x     x x x   x     x x x         x    g

Row #8 starts with the state described in Row #7 and performs Step A5, which moves the cursor back to the beginning of the list and goes back to Step A4. Here, Step A4 is performed three times:

1. Keeps going until it hits a d; tags the d because it is equal to CURRENT; sets CURRENT equal to b, because b comes after this particular d.
2. Keeps going until it hits another b; tags the b because it is equal to CURRENT; sets CURRENT equal to g, because g comes after this particular b.
3. Keeps going until it hits the end of the elements, because it doesn't find another g.

You can see the newly tagged d and b if you compare rows 7 and 8. In particular, the second iteration of Step A4 within Row #8's Step A5 is what causes CURRENT to be set to g.