permlib  0.2.6
Library for permutation computations
 All Classes Functions Variables Typedefs Enumerations Friends
include/permlib/change/conjugating_base_change.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 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_