 |  |  | 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]=s2s1s3s2s5s4s3s5
s4
=(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@kfunigraz.ac.at,
last changed: November 19, 2001
| | | How to handle PERMUTATIONobjects |