Ticket #10976: patch-10976.2.txt

File patch-10976.2.txt, 2.8 KB (added by swenson, 9 years ago)

Patch for 10976

Line 
1diff --git a/sage/groups/perm_gps/permgroup.py b/sage/groups/perm_gps/permgroup.py
2--- a/sage/groups/perm_gps/permgroup.py
3+++ b/sage/groups/perm_gps/permgroup.py
4@@ -90,6 +90,9 @@
5 
6 - Nicolas Borie (2009): Added orbit, transversals, stabiliser and strong_generating_system methods
7 
8+- Christopher Swenson (2011): Added a special case to compute the order efficiently.
9+  (This patch Copyright 2012 Google Inc. All Rights Reserved. )
10+
11 REFERENCES:
12 
13 - Cameron, P., Permutation Groups. New York: Cambridge University
14@@ -132,6 +135,7 @@
15 from sage.misc.package import is_package_installed
16 from sage.sets.finite_enumerated_set import FiniteEnumeratedSet
17 from sage.categories.all import FiniteEnumeratedSets
18+from sage.functions.other import factorial
19 
20 def load_hap():
21     """
22@@ -1289,6 +1293,56 @@
23         return '\\langle ' + \
24                ', '.join([x._latex_() for x in self.gens()]) + ' \\rangle'
25 
26+    def _order(self):
27+        """
28+        This handles a few special cases of computing the subgroup order much
29+        faster than GAP.
30+
31+        This currently operates very quickly for stabilizer subgroups of
32+        permutation groups, for one.
33+
34+        Will return None if the we could not easily compute it.
35+
36+        Author: Christopher Swenson
37+
38+        EXAMPLES::
39+
40+            sage: SymmetricGroup(10).stabilizer(4)._order()
41+            362880
42+            sage: SymmetricGroup(10).stabilizer(4).stabilizer(5)._order()
43+            40320
44+            sage: SymmetricGroup(200).stabilizer(100)._order() == factorial(199)  # this should be very fast
45+            True
46+        """
47+        gens = self.gens()
48+        # only work with more than 1 generator
49+        if not gens or len(gens) < 2:
50+          return None
51+        # check for a wheel-spoke graph, i.e., all generators
52+        # have a length of 2, and they all share a vertex
53+        for g in gens:
54+          if g.order() != 2:
55+            return None
56+        # find the common vertex
57+        g0 = gens[0].cycle_tuples()[0]
58+        g1 = gens[1].cycle_tuples()[0]
59+        a, b = g0
60+        if a not in g1 and b not in g1:
61+          return None
62+        if a in g1:
63+          elem = a
64+        else:
65+          elem = b
66+        # count the elements in the wheel
67+        unique = set()
68+        for g in gens:
69+          a, b = g.cycle_tuples()[0]
70+          if a != elem and b != elem:
71+            return None
72+          unique.add(a)
73+          unique.add(b)
74+        return factorial(len(unique))
75+
76     def order(self):
77         """
78         Return the number of elements of this group.
79@@ -1307,6 +1361,9 @@
80         """
81         if not self.gens() or self.gens() == [self(1)]:
82             return Integer(1)
83+        subgroup_order = self._order()
84+        if subgroup_order is not None:
85+          return subgroup_order
86         return Integer(self._gap_().Size())
87 
88     def random_element(self):