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