zmo man page
zmo — make orbits under a set of permutations
Synopsis
zmo [Options] <Perm> <Orbits>
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 ith 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 ith entry contains the size of the orbit number i.
This file can be fed into zkd(1) or zuk(1). At the end, the program prints a message containing the orbit sizes. Note that at most 20 different orbit sizes are shown here.
Options
- -Q
Quiet, no messages.
- -V
Verbose, more messages.
- -T <MaxTime>
Set CPU time limit
- -g <#Perms>
Set number of permutations. Default: 2.
- -s <Seed>
Set seed point. Default: 1.
Implementation Details
The algorithm uses a fixed size stack to store points. At the beginning, a seed point is searched which has not yet 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.
Input Files
- Perm.{1,2,...}
Permutations
Output Files
- Orbits
Orbit table and sizes.