search

peal / vole

A GAP package for backtrack search in permutation groups with graphs
https://peal.github.io/vole
Mozilla Public License 2.0
8 stars 2 forks source link

Implement a better default refiner for `VoleCon.InGroup(AlternatingGroup(points))` #32

Closed wilfwilson closed 2 years ago

wilfwilson commented 2 years ago

It seems that the default refiner for VoleCon.InGroup(AlternatingGroup(points)) is InGroup-GB, which I guess uses a stabiliser chain? This would explain why this is slow:

gap> A50 := AlternatingGroup(50);;
gap> con := VoleCon.InGroup(A50);;
gap> VoleFind.Group(con) = A50;
true
gap> time;
7228

Using a stabiliser chain for an alternating group is perhaps not the best way of refining for an alternating group. Can we even sensibly refine for an alternating group in (extended) graph backtracking?

Perhaps the refiner should not actually add anything onto the stack, but it should just check for evenness when you reach a leaf node. In particular, perhaps this is what the refiner for VoleCon.IsEven should do (#31), and then VoleCon.InGroup(AlternatingGroup(points)) can just be immediately translated to [VoleCon.IsEven(), VoleCon.MovedPoints(points)].