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.

PermutationListQ	validate a list of integers as reordering of {1,…,n}
PermutationSupport	points moved by a permutation

Basic functionality for permutation lists.

This is a list of 10 integers:

In[1]:=1

✖

https://wolfram.com/xid/0qkd9eayymu-8bxqkz

Out[1]=1

Check that it is indeed a reordering of consecutive integers starting at 1:

In[2]:=2

✖

https://wolfram.com/xid/0qkd9eayymu-q6tti1

Out[2]=2

The support of the permutation list is the list of points not at their natural positions:

In[3]:=3

✖

https://wolfram.com/xid/0qkd9eayymu-ftjvwm

Out[3]=3

If the list of integers is sorted, its support is empty:

In[4]:=4

✖

https://wolfram.com/xid/0qkd9eayymu-3ae3uh

Out[4]=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.

PermutationCycles	convert permutation into disjoint cyclic form
PermutationList	convert permutation into a permutation list

Conversion to and from cyclic form.

Take a permutation list:

In[5]:=5

✖

https://wolfram.com/xid/0qkd9eayymu-56g270

Out[5]=5

Construct the cyclic form of the permutation list. By default, singletons are removed:

In[6]:=6

✖

https://wolfram.com/xid/0qkd9eayymu-yiwaef

Out[6]=6

Choosing any other head keeps singletons:

In[7]:=7

✖

https://wolfram.com/xid/0qkd9eayymu-zfj09p

Out[7]=7

Compare with the following:

In[8]:=8

✖

https://wolfram.com/xid/0qkd9eayymu-moq3w1

In[9]:=9

✖

https://wolfram.com/xid/0qkd9eayymu-g6oexa

Out[9]=9

Vice versa, you can convert a cyclic object into a permutation list of any length:

In[10]:=10

✖

https://wolfram.com/xid/0qkd9eayymu-bk9e8n

Out[10]=10

By default, the length is taken to be the largest integer present in the cycles:

In[11]:=11

✖

https://wolfram.com/xid/0qkd9eayymu-l6f18k

Out[11]=11

The same function allows changing the length of a permutation list without changing its support:

In[12]:=12

✖

https://wolfram.com/xid/0qkd9eayymu-uqflxa

Out[12]=12

In[13]:=13

✖

https://wolfram.com/xid/0qkd9eayymu-k4sd35

Out[13]=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.

Part	return a subexpression, possibly reordering its elements
Permute	permute elements of an expression as given by a permutation
FindPermutation	compute the permutation that takes the first list to the second

Permuting expressions.

Take an expression and a permutation list:

In[14]:=14

✖

https://wolfram.com/xid/0qkd9eayymu-gyaar1

Permute reorders the elements, changing their positions: the first element goes to fourth place etc. The number of elements does not change:

In[16]:=16

✖

https://wolfram.com/xid/0qkd9eayymu-fme89h

Out[16]=16

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[17]:=17

✖

https://wolfram.com/xid/0qkd9eayymu-qqyqxb

Out[17]=17

Permute also accepts cyclic notation in its second argument:

In[18]:=18

✖

https://wolfram.com/xid/0qkd9eayymu-ti6p48

Out[18]=18

It is also possible to use a permutation group, interpreted as a set of permutations:

In[19]:=19

✖

https://wolfram.com/xid/0qkd9eayymu-crla2

Out[19]=19

In[20]:=20

✖

https://wolfram.com/xid/0qkd9eayymu-kof8ug

Out[20]=20

In[21]:=21

✖

https://wolfram.com/xid/0qkd9eayymu-3or0wc

Out[21]=21

The action of Permute can be reverted with FindPermutation, which returns cyclic notation:

In[22]:=22

✖

https://wolfram.com/xid/0qkd9eayymu-0nt597

Out[22]=22

In[23]:=23

✖

https://wolfram.com/xid/0qkd9eayymu-b0myir

Out[23]=23

If you reverse the arguments, you obtain the inverse permutation:

In[24]:=24

✖

https://wolfram.com/xid/0qkd9eayymu-z2xx6o

Out[24]=24

In[25]:=25

✖

https://wolfram.com/xid/0qkd9eayymu-j0ypto

Out[25]=25

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

Part	permutation list product
Ordering	permutation list inverse
Range	identity permutation list
RandomSample	pseudorandom generation of permutation lists

Standard commands reinterpreted for permutation lists.

Take two permutation lists of the same length:

In[26]:=26

✖

https://wolfram.com/xid/0qkd9eayymu-hlu4wr

This is their product, left to right:

In[28]:=28

✖

https://wolfram.com/xid/0qkd9eayymu-kn5gsc

Out[28]=28

The same result can be obtained with Part reversing the order of arguments:

In[29]:=29

✖

https://wolfram.com/xid/0qkd9eayymu-gm08q5

Out[29]=29

The inverse of a permutation list can be computed with InversePermutation, and also with Ordering:

In[30]:=30

✖

https://wolfram.com/xid/0qkd9eayymu-2y0n1c

Out[30]=30

In[31]:=31

✖

https://wolfram.com/xid/0qkd9eayymu-g9f6iz

Out[31]=31

The product of the two permutation lists gives the identity permutation list:

In[32]:=32

✖

https://wolfram.com/xid/0qkd9eayymu-0p1adp

Out[32]=32

The identity permutation list of any length can be expressed with Range:

In[33]:=33

✖

https://wolfram.com/xid/0qkd9eayymu-ygiozh

Out[33]=33

Random reorderings of the identity list are valid permutation lists:

In[34]:=34

✖

https://wolfram.com/xid/0qkd9eayymu-cap984

Out[34]=34

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[35]:=35