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  (6)

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 permutation matrix corresponding to a given permutation list:

Use the "PermutationCycles" property of PermutationMatrix to get the corresponding disjoint cycle representation:

This is equivalent to directly applying PermutationCycles to the permutation list:

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:

This is equivalent to FactorialPower:

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:

Wolfram Research (2010), PermutationCycles, Wolfram Language function, https://reference.wolfram.com/language/ref/PermutationCycles.html (updated 2012).

Text

Wolfram Research (2010), PermutationCycles, Wolfram Language function, https://reference.wolfram.com/language/ref/PermutationCycles.html (updated 2012).

CMS

Wolfram Language. 2010. "PermutationCycles." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2012. https://reference.wolfram.com/language/ref/PermutationCycles.html.

APA

Wolfram Language. (2010). PermutationCycles. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/PermutationCycles.html

BibTeX

@misc{reference.wolfram_2024_permutationcycles, author="Wolfram Research", title="{PermutationCycles}", year="2012", howpublished="\url{https://reference.wolfram.com/language/ref/PermutationCycles.html}", note=[Accessed: 21-December-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_permutationcycles, organization={Wolfram Research}, title={PermutationCycles}, year={2012}, url={https://reference.wolfram.com/language/ref/PermutationCycles.html}, note=[Accessed: 21-December-2024 ]}