permlib  0.2.6
Library for permutation computations
 All Classes Functions Variables Typedefs Enumerations Friends
include/permlib/change/base_transpose.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 BASETRANSPOSE_H_
00034 #define BASETRANSPOSE_H_
00035 
00036 #include <permlib/predicate/pointwise_stabilizer_predicate.h>
00037 #include <permlib/generator/generator.h>
00038 
00039 #include <boost/scoped_ptr.hpp>
00040 #include <boost/iterator/indirect_iterator.hpp>
00041 
00042 namespace permlib {
00043 
00045 
00048 template<class PERM, class TRANS>
00049 class BaseTranspose {
00050 public:
00052     BaseTranspose();
00054     virtual ~BaseTranspose() {}
00055 
00057 
00061     void transpose(BSGS<PERM,TRANS> &bsgs, unsigned int i) const;
00062 
00064     mutable unsigned int m_statScheierGeneratorsConsidered;
00066     mutable unsigned int m_statNewGenerators;
00067 protected:
00068         typedef std::list<typename PERM::ptr> PERMlist;
00069         
00071 
00077     virtual Generator<PERM>* setupGenerator(BSGS<PERM,TRANS> &bsgs, unsigned int i, const PERMlist &S_i, const TRANS &U_i) const = 0;
00078 };
00079 
00080 //
00081 //     ----       IMPLEMENTATION
00082 //
00083 
00084 template<class PERM, class TRANS>
00085 BaseTranspose<PERM,TRANS>::BaseTranspose() 
00086         : m_statScheierGeneratorsConsidered(0), m_statNewGenerators(0)
00087 { }
00088 
00089 template<class PERM, class TRANS>
00090 void BaseTranspose<PERM,TRANS>::transpose(BSGS<PERM,TRANS> &bsgs, unsigned int i) const {
00091         std::vector<dom_int> &B = bsgs.B;
00092         std::vector<TRANS> &U = bsgs.U;
00093 
00094         if (i+1 >= B.size())
00095                 // illegal transpose index
00096                 return;
00097 
00098         PERMlist S_i;
00099         std::copy_if(bsgs.S.begin(), bsgs.S.end(), std::back_inserter(S_i), PointwiseStabilizerPredicate<PERM>(B.begin(), B.begin() + i));
00100 
00101         std::swap(B[i], B[i+1]);
00102 
00103         PERMlist S_i1;
00104         std::copy_if(bsgs.S.begin(), bsgs.S.end(), std::back_inserter(S_i1), PointwiseStabilizerPredicate<PERM>(B.begin(), B.begin() + (i+1)));
00105 
00106         unsigned int targetTransversalSize = U[i+1].size() * U[i].size();
00107 
00108         // new transversal
00109         TRANS U_i(U[i].n());
00110         U_i.orbit(B[i], S_i);
00111         targetTransversalSize /= U_i.size();
00112 
00113         m_statScheierGeneratorsConsidered = 0;
00114         m_statNewGenerators = 0;
00115         TRANS U_i1(U[i+1].n());
00116         U_i1.orbit(B[i+1], S_i1);
00117     boost::scoped_ptr<Generator<PERM> > generator(setupGenerator(bsgs, i, S_i, U_i));
00118     BOOST_ASSERT(generator != 0);
00119     
00120         while (U_i1.size() < targetTransversalSize) {
00121                 bool newGeneratorFound = false;
00122                 while (generator->hasNext()) {
00123                         PERM g = generator->next();
00124                         ++m_statScheierGeneratorsConsidered;
00125                         boost::indirect_iterator<typename PERMlist::iterator> sBegin(S_i1.begin()), sEnd(S_i1.end());
00126                         if (!U_i1.contains(g / B[i+1]) && std::find(sBegin, sEnd, g) == sEnd) {
00127                                 g.flush();
00128                                 boost::shared_ptr<PERM> gen(new PERM(g));
00129                                 S_i1.push_front(gen);
00130                                 ++m_statNewGenerators;
00131                                 U_i1.orbitUpdate(B[i+1], S_i1, gen);
00132                                 newGeneratorFound = true;
00133                                 break;
00134                         }
00135                 }
00136                 if (!newGeneratorFound)
00137                         // we have exhausted all available generators, and we won't find any new ones in the loop
00138                         break;
00139         }
00140         BOOST_ASSERT(U_i1.size() >= targetTransversalSize);
00141 
00142         bsgs.S.insert(bsgs.S.end(), S_i1.begin(), boost::next(S_i1.begin(), m_statNewGenerators));
00143         U[i] = U_i;
00144         U[i+1] = U_i1;
00145 }
00146 
00147 }
00148 
00149 #endif // -- BASETRANSPOSE_H_