Elsevier Science Home
Computer Physics Communications Program Library
Full text online from Science Direct
Programs in Physics & Physical Chemistry
CPC Home

[Licence| Download | New Version Template] aamd_v1_0.gz(1 Kbytes)
Manuscript Title: Computation of group tables for the symmetric groups.
Authors: M.F. Soto Jr., R. Mirman
Program title: NGHBTRNS
Catalogue identifier: AAMD_v1_0
Distribution format: gz
Journal reference: Comput. Phys. Commun. 23(1981)81
Programming language: PL/1.
Computer: IBM 3033.
Operating system: OS/MVT/ASP.
RAM: 194K words
Word size: 8
Peripherals: magnetic tape.
Keywords: General purpose, Algebras, Symmetric group, Permutations, Neighbouring Transpositions, Explicit decompositions.
Classification: 4.2.

Subprograms used:
Cat Id Title Reference
AAMC_v1_0 SYMGRPTB CPC 23(1981)81
AAME_v1_0 SYMSTATS CPC 23(1981)95

Nature of problem:
To find the set of neighbouring transpositions which is equivalent to each permutation of any symmetric group.

Solution method:
The decomposition follows immediately from the theorem proving the the decomposition's existence. The programming is a direct restatement of this result. The outside of the main program is similar to that of SYMGRPTB. The subroutine packages used are ROWLEN, GENPREM and FAC. It is in the subroutine NR of GENPERM that the decomposition is actually found. The main program, inside a DO-loop on the permutations calls the subroutine NR to find the decomposition for the permutation given by the loop index. Once found, it is written out on tape, in the matrix TS (indexed by the permutation and by the transposition index). The decomposition is done twice, once when the permutations are constructed, and again in this loop, before the result is actually stored on tape. This could have been avoided by inserting the matrix TS into GENPERM. But this would have introduced an uneccessary matrix into the other programs using this subroutine. It was felt better to have the inefficiency here than in the more important programs. The maximum number of neighboring transpositions into which a permutation may be decomposed, for each symmetric group, is needed to set the bounds on the relevant matrices. The formula for it was found previously, and appears here as the variable MNT, calculated at the beginning of the program from the formula (actually 1 greater than given by the formula, to avoid problems when bounds of DO-loops are being checked). Program checks The decomposition subroutine is used in several paths of the other programs of this set, so its correctness is checked in checking them. That the transpositions are output properly can be checked by seeing that every permutation (except the identity) is decomposed, that the number of transpositions does not exceed the value given by the formula (the bounds are set so it can), that the neighboring transpositions are correctly decomposed into themselves, and by spot checking by hand. The output is NF, then each NMAX followed by the decomposition of each permutation, in the form of the matrix TS, which is also output on tape.

The program can be used for any symmetric group, for which machine time and storage are available. However, for S(10) and above, there must be some modifications because the numbers then consist of two digits.

Running time:
Through S(4): 12.09s.