zmo - Make Orbits

Command Line

zmo Options [-g NPerms] [-s Seed] Perm Orbits 

Options

Standard options, see Standard Command Line Options

[-g NPerms]

Set the number of permutatins (default is 2).

[-s Seed]

Set the seed point (default is 1).

Perm

Permutation base name.

Orbits

Output file name.

Input Files

Perm.1, Perm.2, ...

Permutations.

Output Files

Orbits

Orbit number and sizes.

Description

This program calculates the orbits under a set of permutations. By default, the program works with two permutations which are read from Perm.1 and Perm.2. Using the `-g' option you can specify a different number of permutations (using the same file name convention). For example,

zmo -g 3 p orbs

reads three permutations from p.1, p.2, and p.3. All permutations must have the same degree.

The result is written to Orbits and consists of two parts:

• The orbit number table. This is an integer matrix with one row and N columns, where N is the degree of the permutations. The i-th entry in this table contains the orbit number of point i. Note: Orbit numbers start with 0.
• The orbit sizes table. This is an integer matrix with one row and K columns, where K is the number of orbits. The i-th entry contains the size of the orbit number i. This file can be fed into zkd or zuk. At the end, the program prints a message containing the orbit sizes. Note that at most 20 different orbit sizes are shown here.

Implementation Details

The algorithm uses a fixed size stack to store points. At the beginning, a seed point is searched which has not yes assigned an orbit number. This point is assigned the next orbit number (beginning with 0) and put on the stack. The main part consists of taking a point from the stack and applying all generators. Any new points obtained in this way are assigned the same orbit number and put on the stack. This step is repeated until the stack is empty, i.e., the orbit is exhausted. Then, the next seed point is seached, and its orbit is calculated, and so on, until all orbits are found. By default, the first seed point is 1. A different seed point may be selected with the "-s" option.

The number of permutations must be less than 50. All permutations must fit into memory at the same time. Also the stack size is limited to 100000 positions.