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