[MathJax on]

2 The Solve Method

The central functionality of the Ferret package is based around the Solve method. This function performs a backtrack search, using the permutation backtracking algorithm, over a set of groups or cosets. Often users will want to use a higher level function which wraps this functionality, such as Stabilizer or Intersection. The solve function accepts a list of groups, and finds their intersection. For efficiency reasons, these groups can be specified in a variety of different ways. As an example, we will consider how to implement Stabilizer(G, S, OnSets), the stabilizer of a set S in a permutation group G using Solve (this is not necessary, as when Ferret is loaded this method is replaced with a Ferret-based implementation). Another way of viewing Stabilizer(G, S, OnSets) is as the intersection of G with Stabilizer(Sym(n), S, OnSets), where Sym(n) is the symmetric group on n points, and n is at least as large as the largest moved point in G. Solve takes a list of objects which represent groups. Two of these are ConInGroup(G), which represents the group G, and ConStabilize(S, OnSets), which represents the group which stabilizes S. We find the intersection of these two groups by Solve([ConInGroup(G), ConStabilize(S, OnSets)]).

2.1 Methods of representing groups in Ferret

Groups and cosets must be represented in a way which Ferret can understand. The following list gives all the types of groups which Ferret accepts, and how to construct them.

2.1-1 ConStabilize

This function creates a Constraint which can be given to Solve (2.1-3). It does not perform any useful actions by itself

In the first form this represents the group which stabilises object under action. The currently allowed actions are OnSets, OnSetsSets, OnSetsDisjointSets, OnSetsTuples, OnTuples, OnPairs and OnDirectedGraph.

In the second form it represents the stabilizer of a partial perm or transformation in the symmetric group on n points.

2.1-2 ConInGroup

This function creates a Constraint which can be given to Solve (2.1-3). It does not perform any useful actions by itself

Represents the set of permutations in a permutation group G, as an argument for Solve (2.1-3).

These methods are both used with Solve:

2.1-3 Solve

Finds the intersection of the list Constraints. Each member of constraints should be a group or coset generated by one of ConInGroup (2.1-2) or ConStabilize (2.1-1). The optional second argument allows configuration options to be passed in. These follow options are supported:

rbaseCellHeuristic (default "smallest")

The cell to be branched on. This is the option which will most effect the time taken to search. the default is usually best. Other options are: "First" (first cell), "Largest" (largest cell), "smallest2" (the 2nd smallest cell), "random" (a random cell) and "randomsmallest" (one of the smallest cells, chosen randomly)

rbaseValueHeuristic (default "smallest")

Choose which cell to branch on within a cell. While this will generally make a big difference to search, it is hard to predict the best value, and small changes to the problem will change the best heuristic. Options are the same as rbaseCellHeuristic.

searchValueHeuristic (default RBase)

The order to branch during search. In general the best order is very hard to predict. Options are "RBase", "InvRBase", "Random", "Sorted" or "Nosort" (which uses the order the values naturally end up in by the algorithm).

searchFirstBranchValueHeuristic (default RBase)

Choose the search order used just on the left-most branches of search. Allows the same options as searchValueHeuristic

stats (default false)

Change the return value to provide a range of information about how search performed (implies recreturn). This information will change between releases.

nodeLimit (default false)

Either false, or an integer which places a limit on the amount of search which should be performed. WARNING: When this option is set to an integer, Ferret will return the current best answer when the limit is reached, which may be a subgroup of the actual result. To know if this limit was reached, set stats to true, and check the nodes.

recreturn (default false)

Return a record containing private information, rather than the group.

only_find_generators (default true)

By default only find the generators of the group. If false, then find all members of the group. This option is only useful for testing. If 'true', then sets 'recreturn' to true.

generated by GAPDoc2HTML