permlib
0.2.6
Library for permutation computations
|
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 BASECONSTRUCTION_H 00034 #define BASECONSTRUCTION_H 00035 00036 #include <map> 00037 #include <algorithm> 00038 00039 #include <permlib/predicate/pointwise_stabilizer_predicate.h> 00040 #include <permlib/predicate/identity_predicate.h> 00041 00042 namespace permlib { 00043 00045 template <class PERM, class TRANS> 00046 class BaseConstruction { 00047 public: 00049 00052 explicit BaseConstruction(dom_int n); 00053 protected: 00055 dom_int m_n; 00056 00058 00066 template <class ForwardIterator, class InputIterator> 00067 void setup(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd, BSGS<PERM, TRANS> &bsgs, std::vector<std::list<typename PERM::ptr> > &S) const; 00068 00070 void mergeGenerators(std::vector<std::list<typename PERM::ptr> >& S, BSGS<PERM,TRANS>& ret) const; 00071 00073 static const unsigned long *empty; 00074 }; 00075 00076 // 00077 // ---- IMPLEMENTATION 00078 // 00079 00080 template <class PERM, class TRANS> 00081 const unsigned long *BaseConstruction<PERM, TRANS>::empty = static_cast<unsigned long*>(0); 00082 00083 00084 template <class PERM, class TRANS> 00085 BaseConstruction<PERM,TRANS>::BaseConstruction(dom_int n) 00086 : m_n(n) 00087 { } 00088 00089 template <class PERM, class TRANS> 00090 template <class ForwardIterator, class InputIterator> 00091 void BaseConstruction<PERM,TRANS>::setup(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd, BSGS<PERM, TRANS> &bsgs, std::vector<std::list<typename PERM::ptr> > &S) const 00092 { 00093 std::vector<dom_int> &B = bsgs.B; 00094 std::vector<TRANS> &U = bsgs.U; 00095 00096 std::list<typename PERM::ptr> nonIdentityGenerators; 00097 std::remove_copy_if(generatorsBegin, generatorsEnd, std::back_inserter(nonIdentityGenerators), IdentityPredicate<PERM>()); 00098 00099 B.insert(B.begin(), prescribedBaseBegin, prescribedBaseEnd); 00100 // extend base so that no group element fixes all base elements 00101 dom_int beta = m_n + 1; 00102 PointwiseStabilizerPredicate<PERM> stab_k(B.begin(), B.end()); 00103 BOOST_FOREACH(const typename PERM::ptr &gen, nonIdentityGenerators) { 00104 if (stab_k(gen)) { 00105 if (bsgs.chooseBaseElement(*gen, beta)) { 00106 B.push_back(beta); 00107 stab_k = PointwiseStabilizerPredicate<PERM>(B.begin(), B.end()); 00108 } 00109 } 00110 } 00111 00112 if (B.empty()) { 00113 B.push_back(0); 00114 U.push_back(TRANS(m_n)); 00115 // the trivial group has an empty generator list 00116 std::list<typename PERM::ptr> S_0; 00117 S.push_back(S_0); 00118 U[0].orbit(B[0], S_0); 00119 return; 00120 } 00121 S.reserve(B.size()); 00122 00123 // pre-compute transversals and fundamental orbits for the current base 00124 unsigned int i = 0; 00125 std::vector<dom_int>::iterator Bit; 00126 for (Bit = B.begin(); Bit != B.end(); ++Bit) { 00127 std::list<typename PERM::ptr> S_i; 00128 std::copy_if(nonIdentityGenerators.begin(), nonIdentityGenerators.end(), 00129 std::back_inserter(S_i), PointwiseStabilizerPredicate<PERM>(B.begin(), Bit)); 00130 00131 U.push_back(TRANS(m_n)); 00132 S.push_back(S_i); 00133 00134 bsgs.orbit(i, S_i); 00135 00136 ++i; 00137 } 00138 } 00139 00140 template <class PERM, class TRANS> 00141 void BaseConstruction<PERM,TRANS>::mergeGenerators(std::vector<std::list<typename PERM::ptr> >& S, BSGS<PERM,TRANS>& ret) const { 00142 std::map<PERM*,typename PERM::ptr> generatorMap; 00143 // merge all generators into one list 00144 BOOST_FOREACH(std::list<typename PERM::ptr> &S_j, S) { 00145 BOOST_FOREACH(typename PERM::ptr &gen, S_j) { 00146 bool found = false; 00147 BOOST_FOREACH(const typename PERM::ptr& genS, ret.S) { 00148 if (*genS == *gen) { 00149 found = true; 00150 generatorMap.insert(std::make_pair(gen.get(), genS)); 00151 break; 00152 } 00153 } 00154 if (!found) { 00155 ret.S.push_back(gen); 00156 generatorMap.insert(std::make_pair(gen.get(), gen)); 00157 } 00158 } 00159 } 00160 00161 BOOST_FOREACH(TRANS& U_i, ret.U) { 00162 U_i.updateGenerators(generatorMap); 00163 } 00164 } 00165 00166 } 00167 00168 #endif // -- BASECONSTRUCTION_H