permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
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
43namespace permlib {
44
46
50template <class PERM, class TRANS, typename Integer = boost::uint64_t>
52public:
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;
92private:
94 Integer m_knownOrder;
95};
96
97//
98// ---- IMPLEMENTATION
99//
100
101template <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
108template <class PERM, class TRANS, typename Integer>
109template <class ForwardIterator>
110inline 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
114template <class PERM, class TRANS, typename Integer>
115template <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_
base class for BSGS construction algorithms
Definition base_construction.h:46
abstract base class for random group element generators
Definition random_generator.h:42
BSGS construction with Random Schreier-Sims algorithm.
Definition random_schreier_sims_construction.h:51
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
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
unsigned int m_statRandomElementsConsidered
number of Schreier generators examined during the last construct call
Definition random_schreier_sims_construction.h:85
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
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
std::vector< TRANS > U
transversals along the stabilizer chain
Definition bsgs_core.h:59
std::vector< dom_int > B
base
Definition bsgs_core.h:55
Represents a base and strong generating set (BSGS)
Definition bsgs.h:89
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:306
unsigned int sift(const PERM &g, PERM &siftee, unsigned int j=0) const
sifts an element through the specified transversal range
Definition bsgs.h:273
bool chooseBaseElement(const PERM &h, dom_int &beta) const
tries to find a new base element
Definition bsgs.h:290
Integer order() const
order of the group
Definition bsgs.h:407