2. Operations with permutations

By default, xPerm` does not check at every step that the objects we are working with are actually permutations because it would take quite some time. The function PermQ is supplied to do that when you require it.

We can validate a permutation with PermQ:

In[20]:=

Out[20]=

In[21]:=

Out[21]=

In[22]:=

Out[22]=

In[23]:=

Out[23]=

In[24]:=

Out[24]=

In[25]:=

Out[25]=

Every permutation has a degree, defined as the largest moved point (signs are not relevant):

In[26]:=

Out[26]=

In[27]:=

Out[27]=

In[28]:=

Out[28]=

In[29]:=

Out[29]=

The identity permutation has degree zero:

In[30]:=

Out[30]=

In[31]:=

Out[31]=

A different concept is that of "length" of a permutation, defined only for notations Perm and Images: it is the length of the list of points. On Cycles and Rules notations length is defined as the degree. This concept is used in internal computations to avoid recomputing the degree of a permutation many times.

In[32]:=

Out[32]=

In[33]:=

Out[33]=

On notations Perm and Images the function NotationOfPerm returns the length (not the degree):

In[34]:=

Out[34]=

It is possible to generate random permutations, of any notation

In[35]:=

Out[35]=

In[36]:=

Out[36]=

The most important operation with permutations is that of their product. I don't like names like Times or similar. I choose a name which is associated only with permutations:

Product of two permutations in the same notation. The (noncommutative) product is from right to left. This means that the product permutation Permute[p1, p2] applied on a given list is equivalent to the application of p1 on that list and then p2 on the result.

In[37]:=

Out[37]=

In[38]:=

Out[38]=

That is the choice in GAP. This example is taken from its manual:

In[39]:=

Out[39]=

In[40]:=

Out[40]=

Inverse permutation:

In[41]:=

Out[41]=

In[42]:=

Out[42]=

Powers of a permutation (equivalent to repeated product with itself). Negative exponents mean powers of the inverse. Note the high efficiency of this function:

In[43]:=

Out[43]=

In[44]:=

Out[44]=

In[45]:=

Out[45]=

In[46]:=

Out[46]=

Permutations can be sorted and compared according to their lists of images:

In[47]:=

Out[47]=

In[48]:=

Out[48]=

In[49]:=

Out[49]=

The function PermEqual checks mathematical equality of permutations comparing images of points and it is thus notation independent:

In[50]:=

Out[50]=

In[51]:=

Out[51]=

All comparatives have been generalized: PermEqual, PermLess, PermGreater, PermLessEqual, PermGreaterEqual, PermOrderedQ, and we can also sort points and permutations as given by a base.

In[52]:=

Images of points or lists of points:

In[53]:=

Out[53]=

In[54]:=

Out[54]=

There is a simple way to generate the identity corresponding to any notation, degree and sign:

In[55]:=

Out[55]=

In[56]:=

Out[56]=

In[57]:=

Out[57]=

ID also represents the identity:

In[58]:=

Out[58]=

We can permute any kind of list, even with repeated elements:

In[59]:=

Out[59]=

Or find a permutation linking two different lists. The result is given in Images notation:

In[60]:=

Out[60]=

Again, note that the order of permutation is very important:

In[61]:=

In[63]:=

Out[63]=

In[64]:=

Out[64]=

In[65]:=

Out[65]=

In[66]:=

Out[66]=

PermQ                    Validate a permutation
PermDeg                    Give the degree of a permutation
PermLength                Give the length of a permutation
RandomPerm                Construct a random permutation of a given degree
Permute                    Product of several permutations
InversePerm                Inverse of a permutation
PowerPermute            Repeated product of a permutation
PermSort                Order permutations according to their images
OnPoints                Compute images of points under a permutation
ID                        Identity permutation
PermuteList                Apply permutation on a given list
PermutationFromTo        Calculate permutation changing one list into other

Basic operations with permutations.

SortB                    Sort points as given by a base
MinB                    Least point of a list as given by a base
PermEqual                Compare permutations
PermGreater                Compare permutations
PermLess                Compare permutations
PermGreaterqual            Compare permutations
PermLessEqual            Compare permutations
PermOrderedQ            Check whether a list of permuations is sorted
PermSort                Sort permutations according to their images

Sorting and comparing permutations.

Created by Mathematica  (May 16, 2008)