Magma provides several tools that sit slightly outside everyday group construction: databases of standard permutation groups, a canonical form for generating sets that lets groups be compared and stored efficiently, and a low-level data structure called the ordered partition stack that underlies backtrack search algorithms.
Permutation Group Databases
Magma includes built-in databases containing all transitive permutation groups of degree up to 32, and all primitive permutation groups of degree up to 4095. These databases let you retrieve a specific group by degree and index rather than constructing it by hand, which is why examples elsewhere often start from a call like TransitiveGroup(6, 4).
> G := TransitiveGroup(6, 4);
> G;
Permutation group G acting on a set of cardinality 6
Order = 12 = 2^2 * 3
(1, 4)(2, 5)
(1, 3, 5)(2, 4, 6)
Canonical Generators
Two permutation groups can be defined by completely different generating sets and still be the same group. Comparing generators directly does not tell you whether two groups are equal, so Magma implements the Hulpke-Linton algorithm to compute a canonical, lexicographically minimal generating set for any permutation group. The underlying ordering of points is the one given by the Labelling intrinsic.
CanonicalGenerators(G) : GrpPerm -> SeqEnum[GrpPermElt], GrpPermElt returns this minimal generating sequence, together with the lexicographically last element of G as a second return value. Two subgroups of the same symmetric group are equal exactly when their canonical generating sequences are equal, which makes this function a practical equality test as well as the mechanism Magma uses internally for fast lookups in sets of permutation groups. The second return value can be used to build a linear ordering of subgroups compatible with ordinary subset ordering.
CanonicalInvariant(G) : GrpPerm -> SeqEnum[SeqEnum], SeqEnum returns the same underlying permutations as CanonicalGenerators, but represented as plain sequences of integers rather than group elements, so they can be compared for equality or lexicographic order without needing a common parent group.
> G := TransitiveGroup(6, 4);
> CanonicalGenerators(G);
[
(2, 5)(3, 6),
(1, 2, 3)(4, 5, 6)
]
(1, 6, 5)(2, 4, 3)
> H := sub<G | Random(G), Random(G)>;
> H;
Permutation group H acting on a set of cardinality 6
(1, 6, 2)(3, 5, 4)
(1, 5, 6)(2, 3, 4)
> CanonicalGenerators(H);
[
(2, 5)(3, 6),
(1, 2, 3)(4, 5, 6)
]
(1, 6, 5)(2, 4, 3)
Although G and H were built from different generators, their canonical generating sequences agree, which proves G and H are in fact the same group.
Ordered Partition Stacks
An ordered partition stack is a specialized data structure for implementing backtrack search algorithms on permutation groups, following the construction described by Jeff Leon. It maintains a stack of successively finer partitions of the set {1..n}, where n is the degree of the stack. Each partition is a sequence of cells; the cells themselves are ordered, but the points within a cell are not, and may be reported in a different order each time the stack is inspected.
OrderedPartitionStack(n) : RngIntElt -> StkPtnOrd creates a new stack of degree n, initially holding a single partition consisting of one cell containing all n points.
The current top partition can be inspected with Degree(P), Height(P) (the number of cells of the finest partition), NumberOfCells(P, h), CellNumber(P, h, x) (which cell contains point x), CellSize(P, h, i), and Cell(P, h, i) (the contents of cell i); in each case the height argument h can be omitted, defaulting to the current height of the stack.
The stack is refined ("pushed") using SplitCell(P, i, x), which splits cell i so that x becomes its own singleton cell, and SplitAllByValues(P, V), which splits every splittable cell according to a sequence of values V, one value per point. Both return true when the stack actually changed. The stack is reduced ("popped") back to an earlier height with Pop(P, h).
> P := OrderedPartitionStack(12);
> P;
Partn stack, degree 12, height 1
[ 1 2 3 4 5 6 7 8 9 10 11 12]
> SplitCell(P, 1, 4);
true
> P;
Partn stack, degree 12, height 2
[ 1 2 3 12 5 6 7 8 9 10 11 | 4]
> V := [i mod 5 + 1: i in [0..11]];
> SplitAllByValues(P, V);
true 119375796
> P;
Partn stack, degree 12, height 6
[ 1 6 11 | 4 | 10 5 | 9 | 8 3 | 12 2 7]
> Pop(P, 4);
> P;
Partn stack, degree 12, height 4
[ 1 6 11 12 2 7 8 3 | 4 | 10 5 | 9]
Splitting cell 1 by the value 4 pulls point 4 out into its own new cell. Splitting all cells by the values in V only manages to split cell 1 further (the other cells were already singletons), producing five new cells numbered 2 through 6, ordered by descending value of V. Popping the stack back to height 4 discards the most recent refinements, restoring an earlier partition.