Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 CycleLengthCounts

Source Notebook

Count the number of cycles for all possible cycle lengths in a permutation

Contributed by: Wolfram Staff (original content by Sriram V. Pemmaraju and Steven S. Skiena)

ResourceFunction["CycleLengthCounts"][p]

returns a SparseArray of the number of cycles of each length in the permutation p.

Details and Options

ResourceFunction["CycleLengthCounts"][p] returns a SparseArray of length n, where n=Length[p].
The list {λ1,λ2,…} given by Normal is also known as permutation type.

Examples

Basic Examples (2) 

Find the number of cycles of each length in a permutation:

In[1]:=
counts = ResourceFunction["CycleLengthCounts"][{1, 2, 4, 3}]
Out[1]=

Use Normal to see the values:

In[2]:=
Normal[counts]
Out[2]=

The identity permutation of length n has n trivial cycles, that is, n 1-cycles:

In[3]:=
n = 10;
In[4]:=
ResourceFunction["CycleLengthCounts"][Range[n]]
Out[4]=
In[5]:=
Normal[%]
Out[5]=

Verify by counting cycles:

In[6]:=
PermutationCycles[Range[n], h]
Out[6]=

Properties and Relations (3) 

A reverse of the even-length identity permutation of length n has 2-cycles:

In[7]:=
ResourceFunction["CycleLengthCounts"][Reverse[Range[10]]] // Normal
Out[7]=

The number of cycles in a permutation is the total of the cycle length counts:

In[8]:=
p = RandomPermutation[20] // PermutationList
Out[8]=
In[9]:=
Total[ResourceFunction["CycleLengthCounts"][p]]
Out[9]=
In[10]:=
Length @@ PermutationCycles[p, Hold]
Out[10]=

The sum is n:

In[11]:=
ResourceFunction["CycleLengthCounts"][ RandomPermutation[20] // PermutationList]
Out[11]=
In[12]:=
Total[MapIndexed[# #2[[1]] &, %]]
Out[12]=

Version History

  • 1.0.0 – 09 July 2020

Related Resources

License Information