TAOCP 1.3.3 Exercise 9
No.
Section 1.3.3: Applications to Permutations
Exercise 9. [10] Both Programs $A$ and $B$ accept the same input and give the answer in essentially the same form. Is the output exactly the same under both programs?
Verified: yes
Solve time: 1m04s
No. The two programs do not necessarily produce exactly the same output.
Program $A$ implements Algorithm $A$, which constructs the answer by choosing the first untagged element encountered in the input and then tracing its orbit. Hence the order of the disjoint cycles in the output, and the choice of the first element written in each cycle, depend on the positions of elements in the original input formula.
Program $B$ computes the same permutation, so the resulting disjoint cycles represent the same mapping. However, cycle notation is not unique; by (3), a cycle may be written starting at any of its elements, and disjoint cycles may be written in different orders. Since Program $B$ processes the data differently, it need not make the same choices as Program $A$ regarding cycle order or starting points. Therefore the two outputs are equivalent representations of the same permutation, but they are not guaranteed to be identical character for character.
Thus the answer is
$$ \boxed{\text{No. The two programs always represent the same permutation, but the printed cycle notation need not be exactly the same.}} $$