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 SIMPLEBASECHANGE_H_ 00034 #define SIMPLEBASECHANGE_H_ 00035 00036 #include <permlib/change/base_change.h> 00037 00038 namespace permlib { 00039 00041 template<class PERM, class TRANS, class BASETRANSPOSE> 00042 class SimpleBaseChange : public BaseChange<PERM,TRANS> { 00043 public: 00045 explicit SimpleBaseChange(const BSGS<PERM,TRANS>&); 00046 00048 template <class InputIterator> 00049 void change(BSGS<PERM,TRANS> &bsgs, InputIterator baseBegin, InputIterator baseEnd, bool skipRedundant = false) const; 00050 }; 00051 00052 // 00053 // ---- IMPLEMENTATION 00054 // 00055 00056 template<class PERM, class TRANS, class BASETRANSPOSE> 00057 SimpleBaseChange<PERM,TRANS,BASETRANSPOSE>::SimpleBaseChange(const BSGS<PERM,TRANS>&) 00058 : BaseChange<PERM,TRANS>() 00059 { } 00060 00061 template<class PERM, class TRANS, class BASETRANSPOSE> 00062 template<class InputIterator> 00063 void SimpleBaseChange<PERM,TRANS,BASETRANSPOSE>::change(BSGS<PERM,TRANS> &bsgs, InputIterator baseBegin, InputIterator baseEnd, bool skipRedundant) const { 00064 if (baseBegin == baseEnd) 00065 return; 00066 00067 const unsigned long origOrder __attribute__((unused)) = bsgs.order(); 00068 BASETRANSPOSE trans; 00069 00070 unsigned int baseTargetPos = 0; 00071 while (baseBegin != baseEnd && baseTargetPos < bsgs.B.size()) { 00072 unsigned long alpha = *baseBegin; 00073 unsigned long beta = bsgs.B[baseTargetPos]; 00074 const bool redundant = skipRedundant && this->isRedundant(bsgs, baseTargetPos, alpha); 00075 00076 if (!redundant && beta != alpha) { 00077 unsigned int pos = bsgs.insertRedundantBasePoint(alpha); 00078 for (; pos > baseTargetPos; --pos) { 00079 trans.transpose(bsgs, pos-1); 00080 ++BaseChange<PERM,TRANS>::m_statTranspositions; 00081 } 00082 } 00083 00084 ++baseBegin; 00085 if (!redundant) 00086 ++baseTargetPos; 00087 } 00088 // insert remaining base points 00089 while (!skipRedundant && baseBegin != baseEnd) { 00090 const unsigned long alpha = *baseBegin; 00091 bsgs.insertRedundantBasePoint(alpha, baseTargetPos); 00092 00093 ++baseBegin; 00094 ++baseTargetPos; 00095 } 00096 00097 bsgs.stripRedundantBasePoints(baseTargetPos); 00098 BaseChange<PERM,TRANS>::m_statScheierGeneratorsConsidered += trans.m_statScheierGeneratorsConsidered; 00099 00100 BOOST_ASSERT(origOrder == bsgs.order()); 00101 } 00102 00103 } 00104 00105 #endif // -- SIMPLEBASECHANGE_H_