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 CONJUGATINGBASECHANGE_H_ 00034 #define CONJUGATINGBASECHANGE_H_ 00035 00036 #include <boost/foreach.hpp> 00037 #include <boost/scoped_ptr.hpp> 00038 #include <boost/cstdint.hpp> 00039 00040 #include <permlib/change/base_change.h> 00041 00042 namespace permlib { 00043 00044 template<class PERM> 00045 struct SymmetricGroup; 00046 00047 template<class PERM,class TRANS> 00048 struct BSGS; 00049 00051 template<class PERM, class TRANS, class BASETRANSPOSE> 00052 class ConjugatingBaseChange : public BaseChange<PERM,TRANS> { 00053 public: 00055 explicit ConjugatingBaseChange(const BSGSCore<PERM,TRANS>&); 00056 00058 template <class InputIterator> 00059 unsigned int change(BSGS<PERM,TRANS> &bsgs, InputIterator baseBegin, InputIterator baseEnd, bool skipRedundant = false) const; 00060 00062 template <class InputIterator> 00063 unsigned int change(SymmetricGroup<PERM> &bsgs, InputIterator baseBegin, InputIterator baseEnd, bool skipRedundant = false) const; 00064 }; 00065 00066 template<class PERM, class TRANS, class BASETRANSPOSE> 00067 ConjugatingBaseChange<PERM,TRANS,BASETRANSPOSE>::ConjugatingBaseChange(const BSGSCore<PERM,TRANS>&) 00068 : BaseChange<PERM,TRANS>() 00069 { } 00070 00071 template<class PERM, class TRANS, class BASETRANSPOSE> 00072 template<class InputIterator> 00073 unsigned int ConjugatingBaseChange<PERM,TRANS,BASETRANSPOSE>::change(BSGS<PERM,TRANS> &bsgs, InputIterator baseBegin, InputIterator baseEnd, bool skipRedundant) const { 00074 if (baseBegin == baseEnd) 00075 return 0; 00076 00077 const boost::uint64_t origOrder __attribute__((unused)) = bsgs.order(); 00078 BASETRANSPOSE trans; 00079 PERM c(bsgs.n); 00080 PERM cInv(bsgs.n); 00082 bool touchedC = false; 00083 00084 unsigned int baseTargetPos = 0; 00085 while (baseBegin != baseEnd && baseTargetPos < bsgs.B.size()) { 00086 const unsigned long alpha = cInv.at(*baseBegin); 00087 const unsigned long beta = bsgs.B[baseTargetPos]; 00088 const bool redundant = skipRedundant && this->isRedundant(bsgs, baseTargetPos, alpha); 00089 00090 if (!redundant && beta != alpha) { 00091 boost::scoped_ptr<PERM> r(bsgs.U[baseTargetPos].at(alpha)); 00092 if (r) { 00093 c ^= *r; 00094 cInv = ~c; 00095 touchedC = true; 00096 } else { 00097 unsigned int pos = bsgs.insertRedundantBasePoint(alpha, baseTargetPos); 00098 for (; pos > baseTargetPos; --pos) { 00099 trans.transpose(bsgs, pos-1); 00100 ++BaseChange<PERM,TRANS>::m_statTranspositions; 00101 } 00102 } 00103 } 00104 if (!redundant) 00105 ++baseTargetPos; 00106 ++baseBegin; 00107 } 00108 00109 // insert remaining base points 00110 while (!skipRedundant && baseBegin != baseEnd) { 00111 const unsigned long alpha = cInv.at(*baseBegin); 00112 bsgs.insertRedundantBasePoint(alpha, baseTargetPos); 00113 00114 ++baseBegin; 00115 ++baseTargetPos; 00116 } 00117 00118 if (touchedC) { 00119 // correct generators by conjugation 00120 BOOST_FOREACH(typename PERM::ptr& g, bsgs.S) { 00121 *g ^= cInv; 00122 *g *= c; 00123 g->flush(); 00124 } 00125 00126 // correct base points 00127 BOOST_FOREACH(dom_int& beta, bsgs.B) { 00128 beta = c.at(beta); 00129 } 00130 } 00131 00132 // always strip redundant base points from the end of the new base 00133 bsgs.stripRedundantBasePoints(baseTargetPos); 00134 BaseChange<PERM,TRANS>::m_statScheierGeneratorsConsidered += trans.m_statScheierGeneratorsConsidered; 00135 00136 if (touchedC) { 00137 for (unsigned int i=0; i<bsgs.U.size(); ++i) { 00138 bsgs.U[i].permute(c, cInv); 00139 } 00140 } 00141 00142 BOOST_ASSERT(bsgs.B.size() == bsgs.U.size()); 00143 BOOST_ASSERT(origOrder == bsgs.order()); 00144 00145 return baseTargetPos; 00146 } 00147 00148 template<class PERM, class TRANS, class BASETRANSPOSE> 00149 template<class InputIterator> 00150 unsigned int ConjugatingBaseChange<PERM,TRANS,BASETRANSPOSE>::change(SymmetricGroup<PERM> &bsgs, InputIterator baseBegin, InputIterator baseEnd, bool skipRedundant) const { 00151 unsigned int basePos = 0; 00152 while (baseBegin != baseEnd) { 00153 //std::cout << "base prefix " << *baseBegin << std::endl; 00154 for (unsigned int i = basePos; i < bsgs.B.size(); ++i) { 00155 if (bsgs.B[i] == *baseBegin) { 00156 std::swap(bsgs.B[i], bsgs.B[basePos]); 00157 //std::cout << " swap " << i << " and " << basePos << std::endl; 00158 break; 00159 } 00160 } 00161 ++basePos; 00162 ++baseBegin; 00163 } 00164 return basePos; 00165 } 00166 00167 } 00168 00169 #endif // -- CONJUGATINGBASECHANGE_H_