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) |