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 (RefLink[Range, paclet:ref/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.

Basic functionality for permutation lists.

This is a list of 10 integers:

list={5,2,3,6,1,7,4,8,9,10}

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

PermutationListQ[list]

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

PermutationSupport[list]

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

PermutationSupport[{1,2,3,4,5,6,7,8}]

Permutation lists can be converted into disjoint cyclic form and vice versa. This is similar to the functions (PackageLink[ToCycles, paclet:Combinatorica/ref/ToCycles, Combinatorica Package Symbol]) and (PackageLink[FromCycles, paclet:Combinatorica/ref/FromCycles, Combinatorica Package Symbol]) in the Combinatorica package in improved form.

Conversion to and from cyclic form.

Take a permutation list:

list={1,24,21,4,17,5,13,26,2,10,27,9,14,3,22,29,28,23,25,18,6,15,11,20,19,8,7,12,16,30}

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

cycles=PermutationCycles[list]

Choosing any other head keeps singletons:

PermutationCycles[list,head]

Compare with the following:

CombinatoricaToCycles[p_]:=Take[#,Position[Rest@#,First@#][[1,1]]]&/@Fold[If[MemberQ[Flatten@#1,#2],#1,Append[#1,NestList[p[[#1]]&,#2,Length@p]]]&,{},p]

RotateRight/@CombinatoricaToCycles[list]

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

PermutationList[cycles,40]

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

PermutationList[cycles]

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

PermutationList[{3,4,2,1,5,6,7},10]

PermutationList[%,5]

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

Permuting expressions.

Take an expression and a permutation list:

expr=F[a,b,c,d,e,f,g];
permlist={4,2,1,3,5};

(RefLink[Permute, paclet:ref/Permute]) reorders the elements, changing their positions: the first element goes to fourth place etc. The number of elements does not change:

Permute[expr,permlist]

(RefLink[Part, paclet:ref/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:

Part[expr,InversePermutation@permlist]

(RefLink[Permute, paclet:ref/Permute]) also accepts cyclic notation in its second argument:

Permute[expr,Cycles[{{1,4,3}}]]

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

group=PermutationGroup[{Cycles[{{1,2}}],Cycles[{{1,3},{2,4}}]}]

GroupOrder[group]

Permute[expr,group]

The action of (RefLink[Permute, paclet:ref/Permute]) can be reverted with (RefLink[FindPermutation, paclet:ref/FindPermutation]), which returns cyclic notation:

Permute[expr,Cycles[{{1,4,3}}]]

FindPermutation[expr,%]

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

FindPermutation[%%,expr]

PermutationProduct[%,%%]

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

Standard commands reinterpreted for permutation lists.

Take two permutation lists of the same length:

list1={9,10,3,7,4,8,5,2,1,6};
list2={3,2,4,10,9,5,7,6,8,1};

This is their product, left to right:

PermutationProduct[list1,list2]

The same result can be obtained with (RefLink[Part, paclet:ref/Part]) reversing the order of arguments:

Part[list2,list1]

The inverse of a permutation list can be computed with (RefLink[InversePermutation, paclet:ref/InversePermutation]), and also with (RefLink[Ordering, paclet:ref/Ordering]):

invlist1=InversePermutation[list1]

Ordering[list1]

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

PermutationProduct[invlist1,list1]

The identity permutation list of any length can be expressed with (RefLink[Range, paclet:ref/Range]):

Range[10]

Random reorderings of the identity list are valid permutation lists:

SeedRandom[1234];RandomSample[Range[10]]

Another important use of permutation lists is the transposition of arrays with (RefLink[Transpose, paclet:ref/Transpose]), which results in a generally different array of permuted dimensions.

Take a rectangular array of nonequal dimensions:

array=Array[a,{2,3,4}]

Dimensions[array]

The transposed array has permuted dimensions:

Dimensions[Transpose[array,{2,3,1}]]

Permute[Dimensions[array],{2,3,1}]