permlib  0.2.6
Library for permutation computations
 All Classes Functions Variables Typedefs Enumerations Friends
include/permlib/construct/random_schreier_sims_construction.h
00001 // ---------------------------------------------------------------------------
00002 //
00003 //  This file is part of PermLib.
00004 //
00005 // Copyright (c) 2009-2011 Thomas Rehn <thomas@carmen76.de>
00006 // All rights reserved.
00007 // 
00008 // Redistribution and use in source and binary forms, with or without
00009 // modification, are permitted provided that the following conditions
00010 // are met:
00011 // 1. Redistributions of source code must retain the above copyright
00012 //    notice, this list of conditions and the following disclaimer.
00013 // 2. Redistributions in binary form must reproduce the above copyright
00014 //    notice, this list of conditions and the following disclaimer in the
00015 //    documentation and/or other materials provided with the distribution.
00016 // 3. The name of the author may not be used to endorse or promote products
00017 //    derived from this software without specific prior written permission.
00018 // 
00019 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
00020 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00021 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
00022 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
00023 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
00024 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00025 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00026 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00027 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00028 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029 //
00030 // ---------------------------------------------------------------------------
00031 
00032 
00033 #ifndef RANDOMSCHREIERSIMSCONSTRUCTION_H_
00034 #define RANDOMSCHREIERSIMSCONSTRUCTION_H_
00035 
00036 #include <permlib/construct/base_construction.h>
00037 #include <permlib/generator/random_generator.h>
00038 #include <permlib/bsgs.h>
00039 
00040 #include <boost/cstdint.hpp>
00041 #include <boost/foreach.hpp>
00042 
00043 namespace permlib {
00044 
00046 
00050 template <class PERM, class TRANS, typename Integer = boost::uint64_t>
00051 class RandomSchreierSimsConstruction : public BaseConstruction<PERM, TRANS> {
00052 public:
00054 
00061         RandomSchreierSimsConstruction(unsigned int n, RandomGenerator<PERM> *rng, Integer knownOrder = 0, 
00062                                                                                                                                  unsigned int minimalConsecutiveSiftingElementCount = 20, unsigned int maxIterationFactor = 10000);
00063 
00065 
00067         template <class ForwardIterator>
00068         BSGS<PERM, TRANS> construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, bool& guaranteedBSGS) const;
00069 
00071 
00081         template <class ForwardIterator, class InputIterator>
00082         BSGS<PERM, TRANS> construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd, bool& guaranteedBSGS) const;
00083 
00085         mutable unsigned int m_statRandomElementsConsidered;
00086 
00088         const unsigned int m_minimalConsecutiveSiftingElementCount;
00089         
00091         const unsigned int m_maxIterationFactor;
00092 private:
00093         RandomGenerator<PERM> *m_rng;
00094         Integer m_knownOrder;
00095 };
00096 
00097 //
00098 //     ----       IMPLEMENTATION
00099 //
00100 
00101 template <class PERM, class TRANS, typename Integer>
00102 RandomSchreierSimsConstruction<PERM,TRANS,Integer>::RandomSchreierSimsConstruction(unsigned int n, RandomGenerator<PERM> *rng, Integer knownOrder, 
00103                                                                                                                                                                                                                                                                                                                                          unsigned int minimalConsecutiveSiftingElementCount, unsigned int maxIterationFactor) 
00104         : BaseConstruction<PERM, TRANS>(n), m_statRandomElementsConsidered(0), m_minimalConsecutiveSiftingElementCount(minimalConsecutiveSiftingElementCount),
00105                 m_maxIterationFactor(maxIterationFactor), m_rng(rng), m_knownOrder(knownOrder)
00106 { }
00107 
00108 template <class PERM, class TRANS, typename Integer>
00109 template <class ForwardIterator>
00110 inline BSGS<PERM, TRANS> RandomSchreierSimsConstruction<PERM,TRANS,Integer>::construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, bool& guaranteedBSGS) const {
00111         return construct(generatorsBegin, generatorsEnd, BaseConstruction<PERM,TRANS>::empty, BaseConstruction<PERM,TRANS>::empty, guaranteedBSGS);
00112 }
00113 
00114 template <class PERM, class TRANS, typename Integer>
00115 template <class ForwardIterator, class InputIterator>
00116 BSGS<PERM, TRANS> RandomSchreierSimsConstruction<PERM, TRANS, Integer>
00117 	::construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd, bool& guaranteedBSGS) const
00118 {
00119         const unsigned int &n = this->m_n;
00120         BSGS<PERM, TRANS> ret(n);
00121         std::vector<dom_int> &B = ret.B;
00122         std::vector<TRANS> &U = ret.U;
00123         std::vector<std::list<typename PERM::ptr> > S;
00124         this->setup(generatorsBegin, generatorsEnd, prescribedBaseBegin, prescribedBaseEnd, ret, S);
00125         
00126         unsigned int consecutiveSiftingElementCount = m_minimalConsecutiveSiftingElementCount;
00127         if (m_knownOrder > 0) {
00128                 // remove consecutive sifting limit if we have the group order as Las Vegas-abort criterion
00129                 consecutiveSiftingElementCount = m_maxIterationFactor;
00130         }
00131         const unsigned int maxIterationCount = B.size() * m_maxIterationFactor;
00132         for (unsigned int it = 0; it < maxIterationCount; ++it) {
00133                 bool isProbableBSGS = true;
00134                 for (unsigned int i = 0; i < consecutiveSiftingElementCount && ret.order() != m_knownOrder; ++i) {
00135                         PERM g = m_rng->next();
00136                         ++m_statRandomElementsConsidered;
00137                         PERM h(n);
00138                         unsigned int j = ret.sift(g, h);
00139                         if (j < B.size() || !h.isIdentity()) {
00140                                 // flush it, because we add it as a generator
00141                                 h.flush();
00142                                 
00143                                 if (j == B.size()) {
00144                                         dom_int gamma = n+1;
00145                                         if (ret.chooseBaseElement(h, gamma)) {
00146                                                 B.push_back(gamma);
00147                                         }
00148                                         BOOST_ASSERT(j < B.size());
00149                                         S.push_back(std::list<typename PERM::ptr>());
00150                                         U.push_back(TRANS(n));
00151                                 }
00152                                 
00153                                 boost::shared_ptr<PERM> hPtr(new PERM(h));
00154                                 S[j].insert(S[j].end(), hPtr);
00155 
00156                                 ret.orbitUpdate(j, S[j], hPtr);
00157                                 isProbableBSGS = false;
00158                                 break;
00159                         }
00160                 }
00161                 if (isProbableBSGS)
00162                         break;
00163         }
00164         
00165         this->mergeGenerators(S, ret);
00166         
00167         // convenience check of group order
00168         guaranteedBSGS = ret.template order<Integer>() == m_knownOrder;
00169         
00170         return ret;
00171 }
00172 
00173 }
00174 
00175 #endif // -- RANDOMSCHREIERSIMSCONSTRUCTION_H_