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 #ifndef PERMLIB_API_H 00033 #define PERMLIB_API_H 00034 00035 #include <permlib/common.h> 00036 #include <permlib/permutation.h> 00037 #include <permlib/bsgs.h> 00038 #include <permlib/transversal/schreier_tree_transversal.h> 00039 #include <permlib/transversal/orbit_set.h> 00040 #include <permlib/construct/schreier_sims_construction.h> 00041 #include <permlib/change/conjugating_base_change.h> 00042 #include <permlib/search/partition/vector_stabilizer_search.h> 00043 #include <permlib/search/classic/set_stabilizer_search.h> 00044 #include <permlib/search/classic/set_image_search.h> 00045 #include <permlib/search/classic/lex_smaller_image_search.h> 00046 #include <permlib/search/orbit_lex_min_search.h> 00047 00048 #include <boost/shared_ptr.hpp> 00049 #include <boost/iterator/counting_iterator.hpp> 00050 00051 namespace permlib { 00052 00053 // --------------------------------------------------------------------- 00054 // useful type definitions 00055 // 00056 00057 typedef Permutation PERMUTATION; 00058 typedef SchreierTreeTransversal<PERMUTATION> TRANSVERSAL; 00059 typedef BSGS<PERMUTATION,TRANSVERSAL> PermutationGroup; 00060 typedef OrbitSet<PERMUTATION,unsigned long> OrbitAsSet; 00061 00062 00063 // --------------------------------------------------------------------- 00064 // BSGS construction 00065 // 00066 00067 template<class InputIterator> 00068 boost::shared_ptr<PermutationGroup> construct(unsigned long n, InputIterator begin, InputIterator end) { 00069 SchreierSimsConstruction<PERMUTATION, TRANSVERSAL> schreierSims(n); 00070 boost::shared_ptr<PermutationGroup> group(new PermutationGroup(schreierSims.construct(begin, end))); 00071 return group; 00072 } 00073 00074 template<class InputIteratorGen, class InputIteratorBase> 00075 boost::shared_ptr<PermutationGroup> construct(unsigned long n, InputIteratorGen beginGen, InputIteratorGen endGen, 00076 InputIteratorBase beginBase, InputIteratorBase endBase) { 00077 SchreierSimsConstruction<PERMUTATION, TRANSVERSAL> schreierSims(n); 00078 boost::shared_ptr<PermutationGroup> group(new PermutationGroup(schreierSims.construct(beginGen, endGen, beginBase, endBase))); 00079 return group; 00080 } 00081 00082 00083 // --------------------------------------------------------------------- 00084 // setwise stabilizer 00085 // 00086 00087 template<class InputIterator> 00088 boost::shared_ptr<PermutationGroup> setStabilizer(const PermutationGroup& group, InputIterator begin, InputIterator end) { 00089 if (begin == end) 00090 return boost::shared_ptr<PermutationGroup>(new PermutationGroup(group)); 00091 00092 PermutationGroup copy(group); 00093 // change the base so that is prefixed by the set 00094 ConjugatingBaseChange<PERMUTATION,TRANSVERSAL, 00095 RandomBaseTranspose<PERMUTATION,TRANSVERSAL> > baseChange(copy); 00096 baseChange.change(copy, begin, end); 00097 00098 // prepare search without DCM pruning 00099 classic::SetStabilizerSearch<BSGS<PERMUTATION,TRANSVERSAL>, TRANSVERSAL> backtrackSearch(copy, 0); 00100 backtrackSearch.construct(begin, end); 00101 00102 // start the search 00103 boost::shared_ptr<PermutationGroup> stabilizer(new PermutationGroup(copy.n)); 00104 backtrackSearch.search(*stabilizer); 00105 return stabilizer; 00106 } 00107 00108 00109 // --------------------------------------------------------------------- 00110 // set image 00111 // 00112 00113 template<class InputIterator> 00114 boost::shared_ptr<Permutation> setImage(const PermutationGroup& group, InputIterator begin, InputIterator end, InputIterator begin2, InputIterator end2) { 00115 PermutationGroup copy(group); 00116 // change the base so that is prefixed by the set 00117 ConjugatingBaseChange<PERMUTATION,TRANSVERSAL, 00118 RandomBaseTranspose<PERMUTATION,TRANSVERSAL> > baseChange(copy); 00119 baseChange.change(copy, begin, end); 00120 00121 // prepare search without DCM pruning 00122 classic::SetImageSearch<BSGS<PERMUTATION,TRANSVERSAL>, TRANSVERSAL> backtrackSearch(copy, 0); 00123 backtrackSearch.construct(begin, end, begin2, end2); 00124 00125 // start the search 00126 return backtrackSearch.searchCosetRepresentative(); 00127 } 00128 00129 00130 // --------------------------------------------------------------------- 00131 // vector stabilizer 00132 // 00133 00134 template<class InputIterator> 00135 boost::shared_ptr<PermutationGroup> vectorStabilizer(const PermutationGroup& group, InputIterator begin, InputIterator end, unsigned int maxEntry = 0) { 00136 std::vector<unsigned int> vector(begin, end); 00137 if (maxEntry == 0) { 00138 BOOST_FOREACH(const unsigned int& v, vector) { 00139 if (v > maxEntry) 00140 maxEntry = v; 00141 } 00142 } 00143 BOOST_ASSERT( maxEntry ); 00144 ++maxEntry; 00145 00146 std::list<unsigned int> nonMaxEntries; 00147 unsigned int i = 0; 00148 BOOST_FOREACH(const unsigned int& v, vector) { 00149 if (v < maxEntry-1) 00150 nonMaxEntries.push_back(i); 00151 ++i; 00152 } 00153 00154 PermutationGroup copy(group); 00155 // change the base so that is prefixed by the set 00156 ConjugatingBaseChange<PERMUTATION,TRANSVERSAL, 00157 RandomBaseTranspose<PERMUTATION,TRANSVERSAL> > baseChange(copy); 00158 baseChange.change(copy, nonMaxEntries.begin(), nonMaxEntries.end()); 00159 00160 // prepare search without DCM pruning 00161 partition::VectorStabilizerSearch<BSGS<PERMUTATION,TRANSVERSAL>, TRANSVERSAL> backtrackSearch(copy, 0); 00162 backtrackSearch.construct(vector.begin(), vector.end(), maxEntry); 00163 00164 // start the search 00165 boost::shared_ptr<PermutationGroup> stabilizer(new PermutationGroup(copy.n)); 00166 backtrackSearch.search(*stabilizer); 00167 return stabilizer; 00168 } 00169 00170 00171 // --------------------------------------------------------------------- 00172 // orbits 00173 // 00174 00175 template<typename PDOMAIN,typename ACTION,typename InputIterator> 00176 std::list<boost::shared_ptr<OrbitSet<PERMUTATION,PDOMAIN> > > orbits(const PermutationGroup& group, InputIterator begin, InputIterator end) { 00177 typedef boost::shared_ptr<OrbitSet<PERMUTATION,PDOMAIN> > ORBIT; 00178 std::list<ORBIT> orbitList; 00179 00180 for (; begin != end; ++begin) { 00181 const PDOMAIN& alpha = *begin; 00182 bool knownElement = false; 00183 BOOST_FOREACH(const ORBIT& orb, orbitList) { 00184 if (orb->contains(alpha)) { 00185 knownElement = true; 00186 break; 00187 } 00188 } 00189 00190 if (knownElement) 00191 continue; 00192 00193 ORBIT orbit(new OrbitSet<PERMUTATION,PDOMAIN>()); 00194 orbit->orbit(alpha, group.S, ACTION()); 00195 orbitList.push_back(orbit); 00196 } 00197 00198 return orbitList; 00199 } 00200 00201 inline std::list<boost::shared_ptr<OrbitAsSet> > orbits(const PermutationGroup& group) { 00202 return orbits<unsigned long, Transversal<PERMUTATION>::TrivialAction>(group, boost::counting_iterator<unsigned long>(0), boost::counting_iterator<unsigned long>(group.n)); 00203 } 00204 00205 // --------------------------------------------------------------------- 00206 // smallest orbit element 00207 // 00208 00209 inline dset smallestSetImage(const PermutationGroup& group, const dset& set) { 00210 OrbitLexMinSearch<PermutationGroup> orbLexMin(group); 00211 return orbLexMin.lexMin(set); 00212 } 00213 00214 00215 template<class InputIteratorB, class InputIteratorZ, class InputIteratorO> 00216 inline bool isNotLexMinSet(PermutationGroup& group, 00217 InputIteratorB baseBegin, InputIteratorB baseEnd, 00218 InputIteratorZ zerosBegin, InputIteratorZ zerosEnd, 00219 InputIteratorO onesBegin, InputIteratorO onesEnd 00220 ) 00221 { 00222 // change the base so that is prefixed by the set 00223 ConjugatingBaseChange<PERMUTATION,TRANSVERSAL, 00224 RandomBaseTranspose<PERMUTATION,TRANSVERSAL> > baseChange(group); 00225 baseChange.change(group, baseBegin, baseEnd); 00226 00227 classic::LexSmallerImageSearch<PermutationGroup, TRANSVERSAL> backtrackSearch(group, 0); 00228 backtrackSearch.construct(zerosBegin, zerosEnd, onesBegin, onesEnd); 00229 00230 // start the search 00231 typename PERMUTATION::ptr g = backtrackSearch.searchCosetRepresentative(); 00232 if (g) { 00233 return true; 00234 } 00235 return false; 00236 } 00237 00238 template<class InputIteratorB, class InputIteratorZ, class InputIteratorO> 00239 inline bool isNotLexMinSet(const PermutationGroup& group, 00240 InputIteratorB baseBegin, InputIteratorB baseEnd, 00241 InputIteratorZ zerosBegin, InputIteratorZ zerosEnd, 00242 InputIteratorO onesBegin, InputIteratorO onesEnd 00243 ) 00244 { 00245 PermutationGroup copy(group); 00246 return isNotLexMinSet(copy, baseBegin, baseEnd, zerosBegin, zerosEnd, onesBegin, onesEnd); 00247 } 00248 00249 00250 } // namespace permlib 00251 00252 00253 #endif // PERMLIB_API_H 00254