Permutation Lists

A possible way of working with permutations is by relating them to the reorderings of the elements of a list. This is the standard point of view in the combinatorial approach to permutations, which shifts the emphasis to the permuted expressions, rather than the permutations themselves. This has always been an implicit interpretation of permutation lists in the Wolfram Language, reorderings of Range[n] for some non-negative integer n. Several standard functions in the Wolfram Language allow basic manipulation of permutation lists, and now other functions have been added to work with permutation lists and convert them into their disjoint cyclic form.

PermutationListQvalidate a list of integers as reordering of
PermutationSupportpoints moved by a permutation

Basic functionality for permutation lists.

This is a list of 10 integers.
In[1]:=
Click for copyable input
Out[1]=
Check that it is indeed a reordering of consecutive integers starting at 1.
In[2]:=
Click for copyable input
Out[2]=
The support of the permutation list is the list of points not at their natural positions.
In[3]:=
Click for copyable input
Out[3]=
If the list of integers is sorted, its support is empty.
In[4]:=
Click for copyable input
Out[4]=

Permutation lists can be converted into disjoint cyclic form and vice versa. This is similar to the functions ToCycles and FromCycles in the Combinatorica package in improved form.

PermutationCyclesconvert permutation into disjoint cyclic form
PermutationListconvert permutation into a permutation list

Conversion to and from cyclic form.

Take a permutation list.
In[5]:=
Click for copyable input
Out[5]=
Construct the cyclic form of the permutation list. By default, singletons are removed.
In[6]:=
Click for copyable input
Out[6]=
Choosing any other head keeps singletons.
In[7]:=
Click for copyable input
Out[7]=
Compare with the following.
In[8]:=
Click for copyable input
In[9]:=
Click for copyable input
Out[9]=
Vice versa, you can convert a cyclic object into a permutation list of any length.
In[10]:=
Click for copyable input
Out[10]=
By default, the length is taken to be the largest integer present in the cycles.
In[11]:=
Click for copyable input
Out[11]=
The same function allows changing the length of a permutation list without changing its support.
In[12]:=
Click for copyable input
Out[12]=
In[13]:=
Click for copyable input
Out[13]=

Permutation lists can be used to permute the parts of an expression with the functions Part and Permute. There are two differences: First, depending on the length of the permutation list, Part may change the number of arguments of the expression, but Permute never changes it. Second, Part and Permute interpret the permutation in different ways.

Partreturn a subexpression, possibly reordering its elements
Permutepermute elements of an expression as given by a permutation
FindPermutationcompute the permutation that takes the first list to the second

Permuting expressions.

Take an expression and a permutation list.
In[14]:=
Click for copyable input
Permute reorders the elements, changing their positions: the first element goes to fourth place etc. The number of elements does not change.
In[15]:=
Click for copyable input
Out[15]=
Part extracts a subexpression, possibly changing the length of the result. In order to obtain an equivalent result the permutation list needs to be inverted.
In[16]:=
Click for copyable input
Out[16]=
Permute also accepts cyclic notation in its second argument.
In[17]:=
Click for copyable input
Out[17]=
It is also possible to use a permutation group, interpreted as a set of permutations.
In[18]:=
Click for copyable input
Out[18]=
In[19]:=
Click for copyable input
Out[19]=
In[20]:=
Click for copyable input
Out[20]=
The action of Permute can be reverted with FindPermutation, which returns cyclic notation.
In[21]:=
Click for copyable input
Out[21]=
In[22]:=
Click for copyable input
Out[22]=
If you reverse the arguments, you obtain the inverse permutation.
In[23]:=
Click for copyable input
Out[23]=
In[24]:=
Click for copyable input
Out[24]=

It is possible to perform permutation operations with permutation lists, using standard commands of the Wolfram Language.

Partpermutation list product
Orderingpermutation list inverse
Rangeidentity permutation list
RandomSamplepseudorandom generation of permutation lists

Standard commands reinterpreted for permutation lists.

Take two permutation lists of the same length.
In[25]:=
Click for copyable input
This is their product, left to right.
In[26]:=
Click for copyable input
Out[26]=
The same result can be obtained with Part reversing the order of arguments.
In[27]:=
Click for copyable input
Out[27]=
The inverse of a permutation list can be computed with InversePermutation, and also with Ordering.
In[28]:=
Click for copyable input
Out[28]=
In[29]:=
Click for copyable input
Out[29]=
The product of the two permutation lists gives the identity permutation list.
In[30]:=
Click for copyable input
Out[30]=
The identity permutation list of any length can be expressed with Range.
In[31]:=
Click for copyable input
Out[31]=
Random reorderings of the identity list are valid permutation lists.
In[32]:=
Click for copyable input
Out[32]=

Another important use of permutation lists is the transposition of arrays with Transpose, which results in a generally different array of permuted dimensions.

Take a rectangular array of nonequal dimensions.
In[33]:=
Click for copyable input
Out[33]=
In[34]:=
Click for copyable input
Out[34]=
The transposed array has permuted dimensions.
In[35]:=
Click for copyable input
Out[35]=
In[36]:=
Click for copyable input
Out[36]=