Function Repository Resource:

PermutationCyclesGraph

Source Notebook

A graph representing cycles and fixed points of a permutation

Contributed by: Wolfram Staff

ResourceFunction["PermutationCyclesGraph"][perm]

constructs a graph of disjoint cycles representing the permutation perm.

Details and Options

ResourceFunction["PermutationCyclesGraph"] accepts the same options as Graph.

Examples

Basic Examples (2) 

Permutation cycles represented as a graph:

In[1]:=
perm = {7, 3, 2, 5, 8, 6, 4, 1};
In[2]:=
ResourceFunction["PermutationCyclesGraph"][perm, VertexLabels -> "Name"]
Out[2]=

Or as a list:

In[3]:=
PermutationCycles[perm]
Out[3]=

Scope (2) 

Cycles graph of a permutation list:

In[4]:=
ResourceFunction[
 "PermutationCyclesGraph"][{6, 3, 2, 4, 5, 10, 8, 9, 1, 7}]
Out[4]=

Permutation represented as Cycles:

In[5]:=
RandomPermutation[10]
Out[5]=
In[6]:=
ResourceFunction["PermutationCyclesGraph"][%]
Out[6]=

Properties and Relations (1) 

Permutation cycles graph can also be constructed, possibly less efficiently, by finding the ordering of a permutation:

In[7]:=
perm = {4, 5, 3, 6, 2, 7, 1, 8};
In[8]:=
Graph[Thread[Ordering[perm] -> Range[8]], VertexLabels -> "Name"]
Out[8]=
In[9]:=
ResourceFunction["PermutationCyclesGraph"][perm, VertexLabels -> "Name"]
Out[9]=

Possible Issues (3) 

PermutationCyclesGraph of a permutation represented as cycles does not include fixed points; neither does the Cycles representation:

In[10]:=
cycles = RandomPermutation[10]
Out[10]=
In[11]:=
ResourceFunction["PermutationCyclesGraph"][cycles]
Out[11]=

Construct a permutation list to include fixed points:

In[12]:=
perm = PermutationList[cycles]
Out[12]=
In[13]:=
ResourceFunction["PermutationCyclesGraph"][perm]
Out[13]=

Alternatively, use an arbitrary head, rather than Cycles, when computing permutation cycles:

In[14]:=
PermutationCycles[cycles, h]
Out[14]=
In[15]:=
ResourceFunction["PermutationCyclesGraph"][%]
Out[15]=

Version History

  • 1.0.0 – 14 September 2020

License Information