permlib  0.2.6
Library for permutation computations
 All Classes Functions Variables Typedefs Enumerations Friends
include/permlib/construct/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 SCHREIERSIMSCONSTRUCTION_H_
00034 #define SCHREIERSIMSCONSTRUCTION_H_
00035 
00036 #include <permlib/construct/base_construction.h>
00037 #include <permlib/bsgs.h>
00038 #include <permlib/generator/schreier_generator.h>
00039 
00040 #include <boost/foreach.hpp>
00041 
00042 namespace permlib {
00043 
00045 template <class PERM, class TRANS>
00046 class SchreierSimsConstruction : public BaseConstruction<PERM, TRANS> {
00047 public:
00049 
00052         explicit SchreierSimsConstruction(unsigned int n);
00053 
00055 
00057         template <class ForwardIterator>
00058         BSGS<PERM, TRANS> construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd) const;
00059 
00061 
00067         template <class ForwardIterator, class InputIterator>
00068         BSGS<PERM, TRANS> construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd) const;
00069 
00071         mutable unsigned int m_statScheierGeneratorsConsidered;
00072 };
00073 
00074 //
00075 //     ----       IMPLEMENTATION
00076 //
00077 
00078 template <class PERM, class TRANS>
00079 SchreierSimsConstruction<PERM,TRANS>::SchreierSimsConstruction(unsigned int n) 
00080         : BaseConstruction<PERM, TRANS>(n), m_statScheierGeneratorsConsidered(0)
00081 { }
00082 
00083 template <class PERM, class TRANS>
00084 template <class ForwardIterator>
00085 inline BSGS<PERM, TRANS> SchreierSimsConstruction<PERM,TRANS>::construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd) const {
00086         return construct(generatorsBegin, generatorsEnd, BaseConstruction<PERM,TRANS>::empty, BaseConstruction<PERM,TRANS>::empty);
00087 }
00088 
00089 template <class PERM, class TRANS>
00090 template <class ForwardIterator, class InputIterator>
00091 BSGS<PERM, TRANS> SchreierSimsConstruction<PERM, TRANS>
00092 	::construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd) const
00093 {
00094         const dom_int &n = this->m_n;
00095         BSGS<PERM, TRANS> ret(n);
00096         std::vector<dom_int> &B = ret.B;
00097         std::vector<TRANS> &U = ret.U;
00098         std::vector<std::list<typename PERM::ptr> > S;
00099         this->setup(generatorsBegin, generatorsEnd, prescribedBaseBegin, prescribedBaseEnd, ret, S);
00100         
00101         std::vector<boost::shared_ptr<SchreierGenerator<PERM, TRANS> > > SchreierGens;
00102         for (unsigned int i = 0; i < B.size(); ++i) {
00103                 BOOST_ASSERT( i < U.size() );
00104                 BOOST_ASSERT( i < S.size() );
00105                 SchreierGens.push_back(boost::shared_ptr<SchreierGenerator<PERM, TRANS> >(new SchreierGenerator<PERM, TRANS>(&U[i], S[i].begin(), S[i].end())));
00106         }
00107         
00108         unsigned int j = B.size();
00109         bool breakUp = false;
00110         while (j >= 1) {
00111                 breakUp = false;
00112                 SchreierGenerator<PERM, TRANS> &sg = *SchreierGens[j-1];
00113                 sg.update(&U[j-1], S[j-1].begin(), S[j-1].end());
00114 
00115                 while (sg.hasNext()) {
00116                         ++m_statScheierGeneratorsConsidered;
00117                         PERMLIB_DEBUG(for(unsigned int jjj=0; jjj<j; ++jjj) std::cout << " ";)
00118                         PERMLIB_DEBUG(std::cout << "schreier j = " << (j-1) << " [" << S[j-1].size() << "," << U[j-1].size() << "]:   ";)
00119                         PERM g = sg.next();
00120                         PERM h(n);
00121                         // sift for S_{j+1}, so use index j here
00122                         unsigned int k = ret.sift(g, h, j);
00123                         if (k < B.size() - j || !h.isIdentity()) {
00124                                 // flush it, because we add it as a generator
00125                                 h.flush();
00126                                 
00127                                 if (j == B.size()) {
00128                                         dom_int gamma = n+1;
00129                                         if (ret.chooseBaseElement(h, gamma)) {
00130                                                 B.push_back(gamma);
00131                                         }
00132                                         BOOST_ASSERT(j < B.size());
00133                                         S.push_back(std::list<typename PERM::ptr>());
00134                                         U.push_back(TRANS(n));
00135                                 }
00136                                 boost::shared_ptr<PERM> hPtr(new PERM(h));
00137                                 S[j].insert(S[j].end(), hPtr);
00138 
00139                                 ret.orbitUpdate(j, S[j], hPtr);
00140                                 if (j >= SchreierGens.size()) {
00141                                         boost::shared_ptr<SchreierGenerator<PERM, TRANS> > localVar(new SchreierGenerator<PERM, TRANS>(&U[j], S[j].begin(), S[j].end()));
00142                                         SchreierGens.push_back(localVar);
00143                                 } else {
00144                                         SchreierGens[j]->update(S[j].size() - 1);
00145                                 }
00146 
00147                                 breakUp = true;
00148                                 ++j;
00149                                 break;
00150                         }
00151                 }
00152                 if (!breakUp)
00153                         --j;
00154         }
00155 
00156         this->mergeGenerators(S, ret);
00157 
00158         return ret;
00159 }
00160 
00161 }
00162 
00163 #endif // -- SCHREIERSIMSCONSTRUCTION_H_