A Partition Stack represents an ordered partition which can be modified in two ways:
A cell in the ordered partition can be split into two pieces
The ordered partition can be reverted to an earlier state, when it had fewer cells.
Let's look at an example! Firstly, we will create a partition stack which partitions [1..8] (Partition Stacks are always defined on a range of integers starting from 1). In the initial state, the partition has a single cell of size 1.
gap> LoadPackage("BacktrackKit", false);; gap> p := PartitionStack(8); [ [ 1, 2, 3, 4, 5, 6, 7, 8 ] ]
In most applications of Partition Stacks, we want to record the list of changes which are made. These are stored in an object known as a Tracer. We will make one.
gap> t := RecordingTracer();;
The main method used for splitting partitions is PS_SplitCellsByFunction. This takes a partition stack, a tracer and a function. It splits each cell of the partition by introducing a cell for each different value the function takes.
gap> PS_SplitCellsByFunction(p, t, {x} -> x mod 3);; gap> p; [ [ 3, 6 ], [ 2, 5, 8 ], [ 1, 4, 7 ] ]
We can further divide the partition with another function
gap> PS_SplitCellsByFunction(p, t, {x} -> x mod 2);; gap> p; [ [ 6 ], [ 2, 8 ], [ 4 ], [ 3 ], [ 5 ], [ 1, 7 ] ]
From this example we can see that whenever an existing cell is split, the new cell is always placed at the end.
There are a range of functions which can be used to find out information about a partition stack,
gap> # Number of cells > PS_Cells(p); 6 gap> # Cells of size 1, in the order they were created > PS_FixedCells(p); [ 1, 4, 5, 3 ] gap> # Contents of the cells of size 1 > PS_FixedPoints(p); [ 6, 3, 5, 4 ] gap> # The contents of a cell, as a slice (a type of list) > PS_CellSlice(p, 2); <slice size=2> gap> AsList(last); [ 2, 8 ]
Note that PS_CellSlice does not make a copy of the list, but gives a "view" inside the partition stack. This means it is fast, but the value will become invalid if another split is made in the Partition Stack. Also, in general the list returned by PS_CellSlice is *NOT* sorted.
We can revert to an earlier state of the partition stack. This includes states we may never have explicitly created, while a cell was being split into pieces.
gap> PS_RevertToCellCount(p, 3); gap> p; [ [ 3, 6 ], [ 2, 5, 8 ], [ 1, 4, 7 ] ] gap> PS_RevertToCellCount(p, 2); gap> p; [ [ 1, 3, 4, 6, 7 ], [ 2, 5, 8 ] ] gap> AsList(PS_CellSlice(p, 1)); [ 6, 3, 4, 1, 7 ]
In partition backtrack, the search takes a list of refiners, each of which represents a group or coset, and calculates their intersection.
Let us begin by calculating the intersection of two groups, \(G\) and \(H\).
gap> LoadPackage("BacktrackKit", false);; gap> G := Group((1,2,3),(4,5,6),(1,4)(2,5)(3,6));; gap> H := Group((1,2,3,4,5,6),(2,3)(4,5));; gap> # Need to make a partition stack to search over > ps := PartitionStack(6);; gap> # We create a refiner for each group > # We have to give this how many points we want the group to act on > rg := BTKit_Refiner.InGroup(G);; gap> rh := BTKit_Refiner.InGroup(H);; gap> # Finally, intersect the groups > BTKit_SimpleSearch(ps, [rg, rh]); Group([ (1,2,3)(4,6,5), (1,4)(2,5)(3,6) ])
The refiner BTKit_Refiner.InGroup represents a group represented as a Permutation Group in GAP. There are many other ways of representing groups. For example, we could calculate a set stabilizer:
gap> # This represents the group which stabilizes the set [3,4,5,6] > ss := BTKit_Refiner.SetStab([3,4,5,6]);; gap> # We can prove this by just "searching" on this group > BTKit_SimpleSearch(ps, [ss]); Group([ (5,6), (4,5), (3,4), (1,2) ]) gap> # We can intersect this with G > BTKit_SimpleSearch(ps, [rg,ss]); Group([ (4,5,6) ]) gap> # We can also intersect G and H and the set stabilizer at the same time! > BTKit_SimpleSearch(ps, [rg,rh,ss]); Group(())
Writing a new refiner requires some understanding of the Partition Backtracking framework by Jeffry Leon. We will give a (very brief, and incomplete!) overview here.
In general, a refiner represents either a group or coset. Here we will consider the case where we are building a coset which represents mapping some permutation \(P\) to another permutation \(Q\) under conjugation. This is a group when \(P=Q\).
To begin, we will just consider the case where \(P=Q\). Then, we need to provide a GAP function \(R\) which, given an ordered partition ps on \(\{1..n\}\) returns a function \(f: \{1..n\} -> O\) (where \(O\) is any valid GAP object) which satisfies the following conditions:
Invariance: Given a permutation \(g\) such that \(P^g=g\), then \(R(ps^g) = R(ps)^g\). Here, we define \(ps^g\) as applying \(g\) to each point in each cell of ps, and we define \((R(ps)^g)(x) := R(ps)(x^g)\).
(TO COMPLETE)
generated by GAPDoc2HTML