 |
 |
 |
How to handle
PERMUTATIONobjects |
How to handle PERMUTATIONobjects
The present subsection contains information on routines, which are
handling PERMUTATION objects.
A routine which builds a quadratic MATRIXobject, the so-called
diagram that corresponds to the permutation in
question:
- NAME: diagramm_permutation
- SYNOPSIS: INT diagramm_permutation(OP perm,mat)
- BUG: perm and mat must be different.
A routine which applies the divided difference labeled by the
PERMUTATIONobject perm to the POLYNOMobject poly, giving a new
POLYNOMobject res:
- NAME: divideddifference
- SYNOPSIS: INT divideddifference(OP perm,poly,res)
A routine that tests whether the two PERMUTATIONobjects a and b
differ only by an elementary transposition:
- NAME: elementarp_permutation
- SYNOPSIS: INT elementarp_permutation(OP a,b)
- RETURN: TRUE or FALSE
- BUG: a and b must be of kind VECTOR
A routine that allows to print a PERMUTATIONobject a to the file
given by the file pointer fp (this works for the kind VECTOR and
ZYKEL of the PERMUTATION object a):
- NAME: fprint_permutation
- SYNOPSIS: INT fprint_permutation(FILE *fp, OP a)
- BUG: There is no test whether a and fp are valid values, it is
recommended to use the general routines fprint or print.
The next routine provides the Lehmer code of the permutation.
Recall that the lehmercode is a bijection between the permutations
and the sequences of natural numbers. Hence, if a is a
PERMUTATIONobject, then b becomes a VECTOR of INTEGER objects, and
if a is a VECTOR of INTEGER objects, then b becomes a
PERMUTATIONobject. It is possible to enter a==b.
- NAME: lehmercode
- SYNOPSIS: INT lehmercode(OP a,b)
Here is a routine that allows to construct a permutation with a
given cycle-type. You enter a PARTITION object, and b becomes a
PERMUTATION object, lying in the class labeled by a. It is possible
to enter a == b; a must be a partition of kind VECTOR
- NAME: m_part_perm
- SYNOPSIS: INT m_part_perm(OP a,b)
Here is an example:
Example:
#include "def.h"
#include "macro.h"
main()
{
OP a;
anfang();
a=callocobject();
scan(PARTITION,a); println(a);
m_part_perm(a,a); println(a);
freeall(a);
ende();
}
Here is a routine that allows you to compute the number of
inversions of the PERMUTATIONobject a. The result is the
INTEGERobject b.
- NAME: numberof_inversionen
- SYNOPSIS: INT numberof_inversionen(OP a,b)
- BUG: a and b must be different.
The next routine allows to apply the PERMUTATIONobject a to a
POLYNOMobject b. It changes the entries of the self-part of b
according to the permutation, the result becomes the POLYNOMobject
c. This works for arbitrary length of a.
- NAME: operate_perm_polynom
- SYNOPSIS: INT operate_perm_polynom(OP a,b,c)
- BUG: c must be different from a and b, the kind of the
PERMUTATIONobject a must be a VECTORobject.
Using the following routine you can apply the PERMUTATIONobject a
to a VECTORobject b. It changes the entries of b according to the
permutation, the result becomes the VECTORobject c. The length of
the PERMUTATION a must be smaller or equal to the length of the
VECTOR b.
- NAME: operate_perm_vector
- SYNOPSIS: INT operate_perm_vector(OP a,b,c)
- BUG: c must be different from a and b, the kind of the
PERMUTATION a must be VECTOR.
The following routine computes the permutation matrix. This is the
matrix with 1 at the place (i,ai) and 0 elsewhere. The
permutation a must be of the kind LIST. a and b may be equal. The
return value is OK if no error occured.
- NAME: perm_matrix
- SYNOPSIS: INT perm_matrix(OP a,b)
Example:
#include "def.h"
#include "macro.h"
main()
{
OP a;
anfang();
a=callocobject();
scan(PERMUTATION,a); println(a);
perm_matrix(a,a); println(a);
freeall(a);
ende();
}
Now we are going to describe a routine that allows to generate at
random permutations of prescribed degree: If a is an INTEGERobject,
then b becomes a random permutation of the given degree a. The kind
of the PERMUTATION b is VECTOR.
- NAME: random_permutation
- SYNOPSIS: INT random_permutation(OP a,b)
- BUG: a and b must be different.
The next routine computes a reduced decomposition of a permutation.
The input is a PERMUTATIONobject perm, and the result is a VECTOR
of INTEGER.
- NAME: rz_perm
- SYNOPSIS: INT rz_perm(OP perm,erg)
- An EXAMPLE: perm = [3,4,6,5,1,2] will give the VECTOR
[2,1,3,2,5,4,3,5,4], which is to read from right to left as a
product of elementary transpositions.
|
[3,4,6,5,1,2]=σ2σ1σ3σ2σ5σ4σ3σ5
σ4 |
|
=(2,3)(1,2)(3,4)(2,3)(5,6)(4,5)(3,4)(5,6)(4,5). |
- BUG: perm and erg must be different.
The next routine computes the signum a of the permutation b. The
signum a is an INTEGERobject.
- NAME: signum_permutation
- SYNOPSIS: INT signum_permutation(OP a,b)
- BUG: a and b must be different.
There is also a routine which tests the installation of
PERMUTATIONobjects:
- NAME: test_perm
- SYNOPSIS: INT test_perm()
We have mentioned, that there are two different kinds of
PERMUTATION objects, they are called VECTOR and ZYKEL. In order to
change one kind into the other, there are the following routines:
- NAMES:
| t_vperm_zperm,
t_VECTOR_ZYKEL |
| t_zperm_vperm,
t_ZYKEL_VECTOR |
- SYNOPSES:
| INT t_vperm_zperm(OP a,b) |
| INT t_zperm_vperm(OP a,b) |
- DESCRIPTION: a is a PERMUATION object of the first kind, i.e.
VECTOR in t_vperm_zperm, b becomes a PERMUTATION object of the
second kind. a and b may be equal. The second names are
synonyms.
The next routine is a test for vexillarity of permutations. It
returns TRUE if perm is a vexillary permutation, i.e. it contains
no subpermutation 2143. part becomes a partition useful for special
purposes, a better method is to specify part=NULL.
- NAME: vexillaryp
- SYNOPSIS: INT vexillaryp(OP perm,part)
- BUG: perm must be of kind VECTOR. perm and part must be
different.
The following routine computes the cyclestructure of the
permutation perm, the result is a PARTITIONobject part, and perm
and part may be equal.
- NAME: zykeltyp
- SYNOPSIS: INT zykeltyp(OP perm,part)
- BUG: perm must be of kind VECTOR.
Example:
#include "def.h"
#include "macro.h"
main()
{
OP a;
anfang();
a=callocobject();
scan(INTEGER,a); println(a);
random_permutation(a,a); println(a);
zykeltyp(a,a); println(a);
freeall(a);
ende();
}
The following routine computes the up-down-sequence of a
PERMUTATION perm, the result is a VECTOR of 1's and 0's, 1 for each
up and 0 for each down.
- NAME: UD_permutation
- SYNOPSIS: INT UD_permutation(OP perm, vector)
- BUG: This routine works only for the VECTOR representation, and
perm and vector must be different.
Now we add an array of general routines that can be
applied to PERMUTATIONobjects, too:
| comp() |
copy() |
dec() |
even() |
| einsp() |
fprint() |
fprintln() |
inc() |
| invers() |
last() |
lehmercode() |
length() |
| mult() |
next() |
objectread() |
objectwrite() |
| odd() |
print() |
println() |
scan() |
| tex() |
|
harald.fripertinger "at" uni-graz.at, May 26,
2011
|
|
|
 |
 |
How to handle
PERMUTATIONobjects |
 |
 |