| | | **Action on the domain of functions** |

#### Action on the domain of functions

A permutation group *G* on the set *X* induces a group action
on the set of all functions from *X* to a set *Y*.
For the following routines you have to specify the operating
group *G* by giving a system of generators. The cardinality *n*
of the set *X*
is the degree of the permutations in *G*. In some cases
you furthermore have to input the cardinality *m* of the set *Y*.
In some cases, when we are dealing with
*characteristic functions*, the cardinality of *Y* is already set
to 2.

A very simple routine generating a set of all representatives
of *G*-orbits on the set of all functions from *{1,...,n} * to
*{1,...,m} * is

INT all_orbits_right(g,m,reps) OP g,m,reps;

where `g`

is a VECTOR of generators of the acting group *G*,
`m`

is the cardinality of *Y* and `reps`

is a VECTOR object
consisting of the representatives of the *G*-orbits.
Such a representative *f* is written as a VECTOR of the form
* [f(1),f(2),...,f(n)]. *

This routine does not use the homomorphism principle, the
surjective method and the Read method for minimizing the number
of minimality tests needed.
At first the *Sims chain* of the acting group is computed
by

INT strong_generators(a,b) OP a,b;

where `a`

is a VECTOR of generators of the permutation group *G*
of degree *n*.
`b`

becomes an *(n+1)´(n+1)* MATRIX which is an upper
triangular matrix.
For *iÎ{1,...,n} * let *C*_{G}(i) be the pointwise
stabilizer of *{1,...,i} *, then the PERMUTATIONs in the
*i-1*-th row of `b`

are representatives of the cosets
*C*_{G}(i-1)/C_{G}(i). For *j³i* the entry `S_M_IJ(b,i-1,j-1)`

is a PERMUTATION *p* such that *p(i)=j*.
The elements in `S_M_IJ(b,i-1,i-1)`

are the identity permutation of
degree *n*.
Then some minimality tests are applied, as described in the last
chapter of [11].

The routine

INT all_orbits_ksubsets(g,k,vec) OP g,k,reps;

computes a transversal of representatives of characteristic functions
of *k*-subsets of *X*. `g`

is a VECTOR of generators of *G*,
`k`

is an INTEGER object, indicating the cardinality of the
subsets, `reps`

is again a VECTOR of representatives.
If *k>n/2* (where *n* is the cardinality of *X*), then it computes
the number of orbits of *n-k*-subsets of *X*.
There is a recursive routine

INT all_orbits_ksubsets_rec(g,k,reps) OP g,k,reps;

which uses the Read method in order to minimize the number of
minimalityt tests needed. It computes a transversal of the
characteristic functions of all *s*-sets *1£s£k*.
Again `g`

is a system of generators of *G*, `k`

indicates *k* and `reps`

is a transversal of these
representatives.

harald.fripertinger@kfunigraz.ac.at,

last changed: November 19, 2001

| | | **Action on the domain of functions** |