diff --git a/sage/groups/perm_gps/permgroup.py b/sage/groups/perm_gps/permgroup.py --- a/sage/groups/perm_gps/permgroup.py +++ b/sage/groups/perm_gps/permgroup.py @@ -90,6 +90,9 @@ - Nicolas Borie (2009): Added orbit, transversals, stabiliser and strong_generating_system methods +- Christopher Swenson (2011): Added a special case to compute the order efficiently. + (This patch Copyright 2012 Google Inc. All Rights Reserved. ) + REFERENCES: - Cameron, P., Permutation Groups. New York: Cambridge University @@ -132,6 +135,7 @@ from sage.misc.package import is_package_installed from sage.sets.finite_enumerated_set import FiniteEnumeratedSet from sage.categories.all import FiniteEnumeratedSets +from sage.functions.other import factorial def load_hap(): """ @@ -1289,6 +1293,56 @@ return '\\langle ' + \ ', '.join([x._latex_() for x in self.gens()]) + ' \\rangle' + def _order(self): + """ + This handles a few special cases of computing the subgroup order much + faster than GAP. + + This currently operates very quickly for stabilizer subgroups of + permutation groups, for one. + + Will return None if the we could not easily compute it. + + Author: Christopher Swenson + + EXAMPLES:: + + sage: SymmetricGroup(10).stabilizer(4)._order() + 362880 + sage: SymmetricGroup(10).stabilizer(4).stabilizer(5)._order() + 40320 + sage: SymmetricGroup(200).stabilizer(100)._order() == factorial(199) # this should be very fast + True + """ + gens = self.gens() + # only work with more than 1 generator + if not gens or len(gens) < 2: + return None + # check for a wheel-spoke graph, i.e., all generators + # have a length of 2, and they all share a vertex + for g in gens: + if g.order() != 2: + return None + # find the common vertex + g0 = gens[0].cycle_tuples()[0] + g1 = gens[1].cycle_tuples()[0] + a, b = g0 + if a not in g1 and b not in g1: + return None + if a in g1: + elem = a + else: + elem = b + # count the elements in the wheel + unique = set() + for g in gens: + a, b = g.cycle_tuples()[0] + if a != elem and b != elem: + return None + unique.add(a) + unique.add(b) + return factorial(len(unique)) + def order(self): """ Return the number of elements of this group. @@ -1307,6 +1361,9 @@ """ if not self.gens() or self.gens() == [self(1)]: return Integer(1) + subgroup_order = self._order() + if subgroup_order is not None: + return subgroup_order return Integer(self._gap_().Size()) def random_element(self):