PermutationCycles

PermutationCycles[perm]

gives a disjoint cycle representation of permutation perm.

Details

  • The input permutation perm can be given as a permutation list or in disjoint cyclic form.
  • A permutation list is a reordering of the consecutive integers {1,2,,n}.
  • PermutationCycles[perm] returns an expression with head Cycles containing a list of cycles, each of the form {p1,p2,,pn}, which represents the mapping of the pi to pi+1. The last point pn is mapped to p1.
  • PermutationCycles[perm,h] returns an expression with head h.
  • The result of PermutationCycles is automatically canonicalized by rotating each cycle so that the smallest point appears first and ordering cycles by the first point.

Examples

open allclose all

Basic Examples  (2)

Cyclic form of a permutation list of length 10:

Identity permutation list:

Scope  (4)

Action on permutation lists:

With a head other than Cycles, singletons are kept:

On other cyclic permutations the input is returned unchanged:

PermutationCycles works efficiently with large permutation lists:

Applications  (2)

Permutation cycles can be considered a sparse representation of permutation lists:

Find the signature of a permutation list:

Properties & Relations  (5)

The collection of cycles returned by PermutationCycles corresponds to the permutation that generates the list from sorted order:

PermutationList gives the inverse of PermutationCycles:

A combination of PermutationCycles and PermutationList adds singletons:

A Wolfram Language implementation of PermutationCycles:

The built-in version is faster:

Number of permutations of the symmetric group with 6 to 1 cycles, including 1-cycles:

Construct an associated polynomial:

Compute the factorization:

Its coefficients are Stirling numbers of the first kind:

Neat Examples  (1)

Average number of cycles for permutation lists of increasing length. Compare with the theoretical estimate:

Introduced in 2010
 (8.0)
 |
Updated in 2012
 (9.0)