({{, (RefLink[PermutationCycles, paclet:ref/PermutationCycles])[perm] 
gives a disjoint cycle representation of permutation perm.}})

OpenersNotesSection(Spacer1)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}.

(RefLink[PermutationCycles, paclet:ref/PermutationCycles])[perm] returns an expression with head (RefLink[Cycles, paclet:ref/Cycles]) containing a list of cycles, each of the form {(Subscript[p, 1]),(Subscript[p, 2]),…,(Subscript[p, n])}, which represents the mapping of the (Subscript[p, i]) to (Subscript[p, i+1]). The last point (Subscript[p, n]) is mapped to (Subscript[p, 1]).

(RefLink[PermutationCycles, paclet:ref/PermutationCycles])[perm,h] returns an expression with head h.

The result of (RefLink[PermutationCycles, paclet:ref/PermutationCycles]) is automatically canonicalized by rotating each cycle so that the smallest point appears first and ordering cycles by the first point.

OpenersPrimaryExamplesSection(Spacer1)Examples  (14)

OpenersExampleSection0(Spacer1)Basic Examples  (2)

Cyclic form of a permutation list of length 10:

PermutationCycles[{2,5,3,6,1,8,7,9,4,10}]

Identity permutation list:

PermutationCycles[{1,2,3,4,5}]

OpenersExampleSection1(Spacer1)Scope  (4)

Action on permutation lists:

PermutationCycles[{6,3,2,5,4,1}]

With a head other than (RefLink[Cycles, paclet:ref/Cycles]), singletons are kept:

PermutationCycles[{2,5,3,6,1,8,7,9,4,10},head]

PermutationCycles[{1,2,3,4,5},Identity]

On other cyclic permutations the input is returned unchanged:

PermutationCycles[Cycles[{{1,3,5},{2,4,6}}]]

(RefLink[PermutationCycles, paclet:ref/PermutationCycles]) works efficiently with large permutation lists:

First@PermutationCycles[RandomSample[Range[1000000]]] // Length

OpenersExampleSection2(Spacer1)Applications  (2)

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

PermutationCycles[{2,3,1,4,5,6,7,8,9,10,12,11,13,14,15,16,17,18,19,20}]

Find the signature of a permutation list:

list=RandomSample[Range[100000]];

Signature[list] == Apply[Times,(-1)^(Length/@PermutationCycles[list,Identity]-1)]

OpenersExampleSection3(Spacer1)Properties & Relations  (5)

The collection of cycles returned by (RefLink[PermutationCycles, paclet:ref/PermutationCycles]) corresponds to the permutation that generates the list from sorted order:

list={7,15,1,9,11,2,12,13,4,6,14,10,5,3,8};

cycs=PermutationCycles[list]

Permute[Sort[list],cycs]===list

(RefLink[PermutationList, paclet:ref/PermutationList]) gives the inverse of (RefLink[PermutationCycles, paclet:ref/PermutationCycles]):

list={15,7,2,12,11,5,6,8,3,14,13,10,9,1,4};

list === PermutationList[PermutationCycles[list]]

A combination of (RefLink[PermutationCycles, paclet:ref/PermutationCycles]) and (RefLink[PermutationList, paclet:ref/PermutationList]) adds singletons:

cycs=Cycles[{{1,5,6},{10,7}}]

PermutationCycles[PermutationList[cycs],Identity]

A Wolfram Language implementation of (RefLink[PermutationCycles, paclet:ref/PermutationCycles]):

combinatoricatocycles[p_]:=Module[{k,j,first,np=p,q=Table[0,{Length[p]}],i},DeleteCases[Table[If[np[[i]]==0,{},j=1;first=np[[i]];np[[i]]=0;
k=q[[j++]]=first;
While[np[[k]]≠0,q[[j++]]=np[[k]];np[[k]]=0;k=q[[j-1]]];
Take[q,j-1]],{i,Length[p]}],_?(#==={}&)]]

The built-in version is faster:

list = RandomSample[Range[10000]];

First[Timing[PermutationCycles[list]]]/First[Timing[combinatoricatocycles[list]]]

Number of permutations of the symmetric group (Subscript[S, 6]) with 6 to 1 cycles, including 1-cycles:

Tally[Length/@(PermutationCycles[#,Identity]&/@Permutations[{1,2,3,4,5,6}])]

Construct an associated polynomial:

Total[Apply[#2 (-x)^#1&,%,{1}]]

Compute the factorization:

Factor[%]

Its coefficients are Stirling numbers of the first kind:

StirlingS1[6,Range[6]]

OpenersExampleSection4(Spacer1)Neat Examples  (1)

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

SeedRandom[0]
DiscretePlot[{Mean[Table[Length@PermutationCycles[RandomSample[Range[n]],Identity],{10}]],Sum[(-1)^(n-k) k StirlingS1[n,k],{k,n}]/n!},{n,50}]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[Cycles, paclet:ref/Cycles])  ▪  (RefLink[PermutationCyclesQ, paclet:ref/PermutationCyclesQ])  ▪  (RefLink[PermutationList, paclet:ref/PermutationList])  ▪  (RefLink[PermutationListQ, paclet:ref/PermutationListQ])}})}})

({{DocumentationFooterIconsRelatedTutorial.png, ({{Tutorials}, {▪(RefLinkPlain[Permutation Lists, paclet:tutorial/PermutationLists])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Permutations, paclet:guide/Permutations])}})}})