Decompose a permutation into a series of swaps (0 i0) . (1 i1) . (2 i2) ...
The decomposition can be naturally represented by the array [i0, i1, i2...].
E.g., the permutation [2 1 0] decomposes to (0 2) . (1 1) . (2 2), meaning that taking element index 2,
then element #1, then element #0 is equivalent to swapping #0 with #2, then swapping #1 with #1 (no-op),
then swapping #2 with #2 (no-op). The decomposition would be [2, 1, 2]. The last swap is always a no-op,
so the decomposition can be shortened to [2, 1].
The advantage of the swap decomposition form is that it lets the permutation be applied to an array in-place.
Decompose a permutation into a series of swaps (0 i0) . (1 i1) . (2 i2) ...
The decomposition can be naturally represented by the array [i0, i1, i2...].
E.g., the permutation [2 1 0] decomposes to (0 2) . (1 1) . (2 2), meaning that taking element index 2, then element #1, then element #0 is equivalent to swapping #0 with #2, then swapping #1 with #1 (no-op), then swapping #2 with #2 (no-op). The decomposition would be [2, 1, 2]. The last swap is always a no-op, so the decomposition can be shortened to [2, 1].
The advantage of the swap decomposition form is that it lets the permutation be applied to an array in-place.