6.9.3  Decomposing a permuation into a product of disjoint cycles: permu2cycles

Any permutation can be decomposed as a sequence of cycles which have no elements in common. For example, the permutation [1,3,4,0,2] can be written as a combination of the cycles [0,1,3] and [2,4].

The permu2cycles command decomposes a permutation into a combination of cycles.

• permu2cycles takes one argument:
  p, a permutation.
• permu2cycles(p) returns the decomposition of p as a product of disjoint cycles. A cycle is represented by a list, a cyclic decomposition is represented by a list of lists.

Examples.

• Input:
  permu2cycles([1,3,4,5,2,0])
  Output:

  ⎡ ⎣

  ⎡ ⎣

  0,1,3,5

  ⎤ ⎦

  ,

  ⎡ ⎣

  2,4

  ⎤ ⎦

  ⎤ ⎦

  In the answer the cycles of size 1 are omitted, except if n−1 is a fixed point of the permutation (this is required to find the value of n from the cycle decomposition).
• Input:
  permu2cycles([0,1,2,4,3,5])
  Output:

  ⎡ ⎣

  ⎡ ⎣

  5

  ⎤ ⎦

  ,

  ⎡ ⎣

  3,4

  ⎤ ⎦

  ⎤ ⎦

• Input:
  permu2cycles([0,1,2,3,5,4])
  Output:

  ⎡ ⎣

  ⎡ ⎣

  4,5

  ⎤ ⎦

  ⎤ ⎦