This page aims to serve as a companion to section 1.3.3 Applications to Permutations in The Art of Computer Programming. It can be easier to understand how these algorithms work by stepping through them and observing the changes made as the algorithm progresses. In some cases, more implementation details are visible than presented in the tables in the original text.

Algorithm A

Multiply permutations in cycle form. (Multi Pass)

A1. [First Pass] Tag all left parentheses, and replace each right parenthesis by a tagged copy of the input symbol that follows its matching left parenthesis.

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. [Set 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 != 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.

References

  • D. E. Knuth, The Art of Computer Programming, vol. 1, 3rd ed. Addison-Wesley, 1997, p. 166.

Algorithm B

Multiply permutations in cycle form. (Single Pass)

B1. [Initialize.] Set T[k] = k for 1 <= k <= n. Also, prepare to scan the input from right to left.

B2. [Next element.] Examine the next element of the input (right to left). If the input has been exhausted, the algorithm terminates. If the element is a ')', set Z = 0 and repeat step B2; if it is a '(', go to B4. Otherwise the element is xi for some i; go on to B3.

B3. [Change T[i].] Exchange Z and T[i]. If this makes T[i] == 0, set j = i. Return to step B2.

B4. [Change T[j].] Set T[j] = Z.(At this point, j is the row that shows a '(' entry in the notation of Table 2, corresponding to the right parenthesis that matches the left parenthesis just scanned.) Return to step B2.

References

  • D. E. Knuth, The Art of Computer Programming, vol. 1, 3rd ed. Addison-Wesley, 1997, p. 173.

Algorithm I

Inverse in place.

I1. [Initialize.] Set m = n, j = -1.

I2. [Next element.] Set i = X[m]. If i < 0, go to step I5 (the element has already been processed).

I3. [Invert one.] (At this point j < 0 and i == X[m]. If m is not the largest element of its cycle, the original permutation had X[-j] == m.) Set X[m] = j, j = -m, m = i, i = X[m].

I4. [End of cycle?] If i > 0, go back to I3 (the cycle has not ended); otherwise set i = j. (In the latter case, the original permutation had X[-j] == m, and m is the largest in its cycle.)

I5. [Store final value.] Set X[m] = -i. (Originally X[-i] was equal to m.)

I6. [Loop on m.] Decrease m by 1. If m > 0, go back to I2; otherwise the algorithm terminates.

References

Algorithm J

Inverse in place.

J1. [Negate all.] Set X[k] = -X[k], for 1 <= k <= n. Also set m = n.

J2. [Initialize j.] Set j = m.

J3. [Find negative entry.] Set i = X[j]. If i > 0, set j = i and repeat this step.

J4. [Invert.] Set X[j] = X[-i], X[-i] = m.

J5. [Loop on m.] Decrease m by 1; if m > 0, go back to J2. Otherwise the algorithm terminates.

References

  • D. E. Knuth, The Art of Computer Programming, vol. 1, 3rd ed. Addison-Wesley, 1997, p. 177.