Permutations

Permutations are basic elements in algebra. They have a natural non-commutative product (as matrices do as well), and hence can encode highly nontrivial structures in a compact way. Permutations provide a way of representing any finite group, which makes them key tools in many applications in mathematics, science, engineering, or even art. In particular, permutations play a central role in the description of discrete symmetries.

Permutations are, roughly speaking, reorderings of a set of elements, or more precisely, bijections from the set onto itself. Only sets with a finite number of elements will be considered. The number of possible permutations of a set of elements is , and therefore for a moderate number there are already permutations, which is almost .

This tutorial discusses how to manipulate permutations in cyclic notation in Mathematica, and "Permutation Lists" describes the relation to permutation list notation. Other tutorials, "Permutation Groups" and "Named Groups", describe how to work with groups of permutations, and "Group Theory Algorithms" shows how to extract information from them without listing all elements of the group.

Representation of a Permutation

Cycleshead denoting a permutation in disjoint cyclic form
PermutationCyclesQvalidate a permutation

Representation of a permutation.

The disjoint cyclic representation of a permutation has the form Cycles[{cyc1, cyc2, ...}] in Mathematica, where the cycles are disjoint lists of positive integers. Integers are mapped under the permutation to their right neighbors, and the last integer of a cycle is mapped to the first member of that cycle. Integers not present in the cycles are mapped onto themselves, though they could also appear in cycles of length 1, which are called singletons or fixed points. The ordering of cycles is immaterial, and individual cycles can be rotated without changing the permutation. Permutations are automatically canonicalized so that the smallest integer of each cycle comes first, and then cycles are sorted by their first integer.

This is a permutation with two cycles and .
In[1]:=
Click for copyable input
Out[1]=
This represents the same permutation. Singletons and empty cycles are removed.
In[2]:=
Click for copyable input
Out[2]=
Any permutation with only singletons represents the identity.
In[3]:=
Click for copyable input
Out[3]=

With permutations containing explicit lists of numbers, there is automatic syntax checking. In other cases, you can use the function PermutationCyclesQ to check the syntax.

The cycles must be disjoint.
In[4]:=
Click for copyable input
Out[4]=
Integers must be positive.
In[5]:=
Click for copyable input
Out[5]=
Numbers other than integers are not accepted.
In[6]:=
Click for copyable input
Out[6]=
This is a valid permutation in cyclic form.
In[7]:=
Click for copyable input
Out[7]=
These are invalid permutations, for obvious reasons.
In[8]:=
Click for copyable input
Out[8]=
In[9]:=
Click for copyable input
Out[9]=
In[10]:=
Click for copyable input
Out[10]=

Permutation Action and Support

If a permutation perm maps the integer to the integer , then is called the image of under the permutation perm. Images are computed with the function PermutationReplace.

PermutationReplaceimage of an integer under a permutation

Standard action of permutations on other expressions.

This is the image of 3.
In[11]:=
Click for copyable input
Out[11]=
These are the images of the first 6 integers.
In[12]:=
Click for copyable input
Out[12]=

The standard action of permutations can be extended to other objects, like other permutations or arrays of integers or permutations.

Map integers of the first permutation under the second permutation (conjugation).
In[13]:=
Click for copyable input
Out[13]=

Permutations are not assumed to belong to any particular finite group, not even a particular symmetric group of some degree. However, there is the concept of support, defined as the set of integers moved by the permutation, which better describes where a permutation acts naturally.

PermutationSupportset of integers moved by a permutation
PermutationLengthnumber of integers moved by a permutation
PermutationMaxlargest integer moved by a permutation
PermutationMinsmallest integer moved by a permutation

Permutation support functions.

The following permutation moves only five points.
In[14]:=
Click for copyable input
Out[14]=
In[15]:=
Click for copyable input
Out[15]=
In[16]:=
Click for copyable input
Out[16]=
The largest moved point is 55.
In[17]:=
Click for copyable input
Out[17]=
The smallest moved point is 4.
In[18]:=
Click for copyable input
Out[18]=
RandomPermutationgenerate pseudorandom permutations

Random generation of permutations.

Generate a random permutation moving (perhaps not all) integers .
In[19]:=
Click for copyable input
Out[19]=
Generate several random permutations in a given group.
In[20]:=
Click for copyable input
Out[20]=

Permute Parts of an Expression

Permutations can be used to permute the parts of other expressions with the function Permute. Integer being mapped to integer is interpreted as part being moved to part . Permute never changes the number of elements of an expression, it simply reorders them.

Permutepermute parts of an expression
FindPermutationreturn permutation linking two expressions with the same elements

Reordering under a permutation.

Swap the first and last letters of the alphabet.
In[21]:=
Click for copyable input
Out[21]=
Permute three parts of an expression, leaving the rest invariant.
In[22]:=
Click for copyable input
In[24]:=
Click for copyable input
Out[24]=
The same result can be obtained using a permutation list representation and the function Part.
In[25]:=
Click for copyable input
Out[25]=
In[26]:=
Click for copyable input
Out[26]=
In[27]:=
Click for copyable input
Out[27]=
However, the length of the permutation list must match that of the expression.
In[28]:=
Click for copyable input
Out[29]=
In[30]:=
Click for copyable input
Out[30]=
Permutation lists can also be used with the function Permute.
In[31]:=
Click for copyable input
Out[31]=
Vice versa, given two expressions with the same elements, a permutation linking them can be computed.
In[32]:=
Click for copyable input
In[34]:=
Click for copyable input
Out[34]=
In[35]:=
Click for copyable input
Out[35]=
Reversing the two arguments gives the inverse permutation.
In[36]:=
Click for copyable input
Out[36]=
With a single argument, FindPermutation returns the permutation that generates an expression from its canonical order.
In[37]:=
Click for copyable input
Out[37]=
In[38]:=
Click for copyable input
Out[38]=

Product of Permutations

PermutationProductproduct of permutations (non-commutative)
InversePermutationinverse of a permutation
PermutationPowerinteger power (product with itself or inverse) of a permutation
PermutationOrderlowest positive power of a permutation yielding the identity

Product of permutations.

There are two possible conventions for the product of two permutations and , depending on whether PermutationProduct[perm1, perm2] means that you first use and then (this is called a left-to-right product) or you first use and then (right-to-left product). With the convention of writing images as right neighbors in cycles, Mathematica's PermutationProduct effectively is a left-to-right product.

The product of permutations is not commutative.
In[39]:=
Click for copyable input
In[41]:=
Click for copyable input
Out[41]=
In[42]:=
Click for copyable input
Out[42]=
PermutationReplace acts from the right, consistent with the left-to-right character of the product.
In[43]:=
Click for copyable input
Out[43]=
In[44]:=
Click for copyable input
Out[44]=
Permute also acts from the right.
In[45]:=
Click for copyable input
Out[45]=
In[46]:=
Click for copyable input
Out[46]=

After the permutation product law has been given, the associated concepts of inversion, power, and order can be immediately defined. For permutations of finite support, the order is always finite.

You can compute inverses of permutations.
In[47]:=
Click for copyable input
Out[47]=
In[48]:=
Click for copyable input
Out[48]=
And you can compute powers of them. Negative powers are powers of the inverse.
In[49]:=
Click for copyable input
Out[49]=
In[50]:=
Click for copyable input
Out[50]=
In[51]:=
Click for copyable input
Out[51]=
In[52]:=
Click for copyable input
Out[52]=
The order of a permutation is the lowest positive power such that the identity permutation is obtained.
In[53]:=
Click for copyable input
Out[53]=
In[54]:=
Click for copyable input
Out[54]=
Another example.
In[55]:=
Click for copyable input
In[56]:=
Click for copyable input
Out[56]=
In[57]:=
Click for copyable input
Out[57]=
This means that (for permutations of finite support) the inverse is always a positive power of the permutation.
In[58]:=
Click for copyable input
Out[58]=

Equality and Sorting of Permutations

As is standard in Mathematica, there are two types of equality tests: structural equality (SameQ) and mathematical equality (Equal). The former can compare any two expressions, but the latter will only return True or False when comparing mathematical expressions with the same type of value. The same happens when ordering expressions: there is structural (canonical) order, implemented through Order and OrderedQ, and there is mathematical order, given by Less and related functions.

Any two permutations of any degree can always be tested for equality and ordering. This is done by comparing sequentially the images of the integers 1, 2, 3, ... . The smaller permutation corresponds to smaller images, such that the identity permutation always comes first. This defines mathematical order. Canonical order follows standard rules, and may differ from mathematical order.

Take two permutations.
In[59]:=
Click for copyable input
These are the images of the first 7 integers under them.
In[61]:=
Click for copyable input
Out[61]=
In[62]:=
Click for copyable input
Out[62]=
Permutation must be sorted before because its second image is smaller.
In[63]:=
Click for copyable input
Out[63]=
The standard canonical order will sort smaller expressions first.
In[64]:=
Click for copyable input
Out[64]=
You can sort permutations using mathematical order by using an "ordering function".
In[65]:=
Click for copyable input
Out[65]=
You can check whether a list of permutations is sorted.
In[66]:=
Click for copyable input
Out[66]=

Special Types of Permutations

There are special types of permutations. In many cases the cyclic notation allows simple constructions to detect them.

Involutions contain only cycles of maximal length 2.
In[67]:=
Click for copyable input
In[68]:=
Click for copyable input
Out[68]=
In[69]:=
Click for copyable input
Out[69]=
A permutation is a derangement of degree if all integers are moved.
In[70]:=
Click for copyable input
In[71]:=
Click for copyable input
Out[71]=
In[72]:=
Click for copyable input
Out[72]=
A permutation is said to be circular of degree if it consists of a single cycle of length .
In[73]:=
Click for copyable input
In[74]:=
Click for copyable input
Out[74]=
In[75]:=
Click for copyable input
Out[75]=

From the cyclic notation of a permutation it is also simple to construct a decomposition into transpositions, that is, permutations with a single cycle of length 2.

These functions construct a list of transpositions whose product is the original permutation.
In[76]:=
Click for copyable input
In[78]:=
Click for copyable input
In[79]:=
Click for copyable input
Out[79]=
In[80]:=
Click for copyable input
Out[80]=
Such decomposition into transpositions is not unique, but the parity (even or odd) of the number of transpositions is invariant. This is called the signature of the permutation.
In[81]:=
Click for copyable input
In[82]:=
Click for copyable input
Out[82]=
In[83]:=
Click for copyable input
Out[83]=
The previous example permutation perm was decomposed into five transpositions, an odd number. Hence it has signature .
In[84]:=
Click for copyable input
Out[84]=
New to Mathematica? Find your learning path »
Have a question? Ask support »