permlib  0.2.9
Library for permutation computations
random_schreier_sims_construction.h
1 // ---------------------------------------------------------------------------
2 //
3 // This file is part of PermLib.
4 //
5 // Copyright (c) 2009-2011 Thomas Rehn <thomas@carmen76.de>
6 // All rights reserved.
7 //
8 // Redistribution and use in source and binary forms, with or without
9 // modification, are permitted provided that the following conditions
10 // are met:
11 // 1. Redistributions of source code must retain the above copyright
12 // notice, this list of conditions and the following disclaimer.
13 // 2. Redistributions in binary form must reproduce the above copyright
14 // notice, this list of conditions and the following disclaimer in the
15 // documentation and/or other materials provided with the distribution.
16 // 3. The name of the author may not be used to endorse or promote products
17 // derived from this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 //
30 // ---------------------------------------------------------------------------
31 
32 
33 #ifndef RANDOMSCHREIERSIMSCONSTRUCTION_H_
34 #define RANDOMSCHREIERSIMSCONSTRUCTION_H_
35 
36 #include <permlib/construct/base_construction.h>
37 #include <permlib/generator/random_generator.h>
38 #include <permlib/bsgs.h>
39 
40 #include <boost/cstdint.hpp>
41 #include <boost/foreach.hpp>
42 
43 namespace permlib {
44 
46 
50 template <class PERM, class TRANS, typename Integer = boost::uint64_t>
51 class RandomSchreierSimsConstruction : public BaseConstruction<PERM, TRANS> {
52 public:
54 
61  RandomSchreierSimsConstruction(unsigned int n, RandomGenerator<PERM> *rng, Integer knownOrder = 0,
62  unsigned int minimalConsecutiveSiftingElementCount = 20, unsigned int maxIterationFactor = 10000);
63 
65 
67  template <class ForwardIterator>
68  BSGS<PERM, TRANS> construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, bool& guaranteedBSGS) const;
69 
71 
81  template <class ForwardIterator, class InputIterator>
82  BSGS<PERM, TRANS> construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd, bool& guaranteedBSGS) const;
83 
85  mutable unsigned int m_statRandomElementsConsidered;
86 
89 
91  const unsigned int m_maxIterationFactor;
92 private:
93  RandomGenerator<PERM> *m_rng;
94  Integer m_knownOrder;
95 };
96 
97 //
98 // ---- IMPLEMENTATION
99 //
100 
101 template <class PERM, class TRANS, typename Integer>
103  unsigned int minimalConsecutiveSiftingElementCount, unsigned int maxIterationFactor)
104  : BaseConstruction<PERM, TRANS>(n), m_statRandomElementsConsidered(0), m_minimalConsecutiveSiftingElementCount(minimalConsecutiveSiftingElementCount),
105  m_maxIterationFactor(maxIterationFactor), m_rng(rng), m_knownOrder(knownOrder)
106 { }
107 
108 template <class PERM, class TRANS, typename Integer>
109 template <class ForwardIterator>
110 inline BSGS<PERM, TRANS> RandomSchreierSimsConstruction<PERM,TRANS,Integer>::construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, bool& guaranteedBSGS) const {
111  return construct(generatorsBegin, generatorsEnd, BaseConstruction<PERM,TRANS>::empty, BaseConstruction<PERM,TRANS>::empty, guaranteedBSGS);
112 }
113 
114 template <class PERM, class TRANS, typename Integer>
115 template <class ForwardIterator, class InputIterator>
117  ::construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd, bool& guaranteedBSGS) const
118 {
119  const unsigned int &n = this->m_n;
120  BSGS<PERM, TRANS> ret(n);
121  std::vector<dom_int> &B = ret.B;
122  std::vector<TRANS> &U = ret.U;
123  std::vector<std::list<typename PERM::ptr> > S;
124  this->setup(generatorsBegin, generatorsEnd, prescribedBaseBegin, prescribedBaseEnd, ret, S);
125 
126  unsigned int consecutiveSiftingElementCount = m_minimalConsecutiveSiftingElementCount;
127  if (m_knownOrder > 0) {
128  // remove consecutive sifting limit if we have the group order as Las Vegas-abort criterion
129  consecutiveSiftingElementCount = m_maxIterationFactor;
130  }
131  const unsigned int maxIterationCount = B.size() * m_maxIterationFactor;
132  for (unsigned int it = 0; it < maxIterationCount; ++it) {
133  bool isProbableBSGS = true;
134  for (unsigned int i = 0; i < consecutiveSiftingElementCount && ret.order() != m_knownOrder; ++i) {
135  PERM g = m_rng->next();
136  ++m_statRandomElementsConsidered;
137  PERM h(n);
138  unsigned int j = ret.sift(g, h);
139  if (j < B.size() || !h.isIdentity()) {
140  // flush it, because we add it as a generator
141  h.flush();
142 
143  if (j == B.size()) {
144  dom_int gamma = n+1;
145  if (ret.chooseBaseElement(h, gamma)) {
146  B.push_back(gamma);
147  }
148  BOOST_ASSERT(j < B.size());
149  S.push_back(std::list<typename PERM::ptr>());
150  U.push_back(TRANS(n));
151  }
152 
153  boost::shared_ptr<PERM> hPtr(new PERM(h));
154  S[j].insert(S[j].end(), hPtr);
155 
156  ret.orbitUpdate(j, S[j], hPtr);
157  isProbableBSGS = false;
158  break;
159  }
160  }
161  if (isProbableBSGS)
162  break;
163  }
164 
165  this->mergeGenerators(S, ret);
166 
167  // convenience check of group order
168  guaranteedBSGS = ret.template order<Integer>() == m_knownOrder;
169 
170  return ret;
171 }
172 
173 }
174 
175 #endif // -- RANDOMSCHREIERSIMSCONSTRUCTION_H_
abstract base class for random group element generators
Definition: random_generator.h:42
void orbitUpdate(unsigned int j, const PERMlist &generators, const typename PERM::ptr &g)
updates the j-th fundamental orbit with the given orbit generators and a new generator g ...
Definition: bsgs.h:305
bool chooseBaseElement(const PERM &h, dom_int &beta) const
tries to find a new base element
Definition: bsgs.h:289
const unsigned int m_maxIterationFactor
factor limiting the number of maximal iterations depeding on the initial base size ...
Definition: random_schreier_sims_construction.h:91
BSGS construction with Random Schreier-Sims algorithm.
Definition: random_schreier_sims_construction.h:51
RandomSchreierSimsConstruction(unsigned int n, RandomGenerator< PERM > *rng, Integer knownOrder=0, unsigned int minimalConsecutiveSiftingElementCount=20, unsigned int maxIterationFactor=10000)
constructor
Definition: random_schreier_sims_construction.h:102
Integer order() const
order of the group
Definition: bsgs.h:406
unsigned int sift(const PERM &g, PERM &siftee, unsigned int j=0) const
sifts an element through the specified transversal range
Definition: bsgs.h:272
std::vector< dom_int > B
base
Definition: bsgs_core.h:55
base class for BSGS construction algorithms
Definition: base_construction.h:46
BSGS< PERM, TRANS > construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, bool &guaranteedBSGS) const
constructs a probable BSGS for group given by generators with no base prescribed
Definition: random_schreier_sims_construction.h:110
Represents a base and strong generating set (BSGS)
Definition: bsgs.h:58
std::vector< TRANS > U
transversals along the stabilizer chain
Definition: bsgs_core.h:59
const unsigned int m_minimalConsecutiveSiftingElementCount
number of elements that have to sift through constructed BSGS consecutively that it is returned as a ...
Definition: random_schreier_sims_construction.h:88
unsigned int m_statRandomElementsConsidered
number of Schreier generators examined during the last construct call
Definition: random_schreier_sims_construction.h:85
Definition: abstract_bsgs.h:49