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 DADE_INVARIANTS_H_ 00034 #define DADE_INVARIANTS_H_ 00035 00036 #include <permlib/transversal/orbit_set.h> 00037 #include <permlib/invariant/linear_form_list.h> 00038 00039 namespace permlib { 00040 00042 template<class BSGSIN> 00043 class DadeInvariants { 00044 public: 00045 typedef typename BSGSIN::PERMtype PERM; 00046 typedef typename BSGSIN::TRANStype TRANS; 00047 00049 DadeInvariants(const BSGSIN& bsgs); 00050 00052 virtual ~DadeInvariants(){} 00053 00055 00059 void invariants(std::list<LinearFormList>& invariantList, unsigned int maximalDegree = 0) const; 00060 private: 00061 const BSGSIN& m_bsgs; 00062 }; 00063 00064 // 00065 // IMPLEMENTATION 00066 // 00067 00068 00069 template<class BSGSIN> 00070 DadeInvariants<BSGSIN>::DadeInvariants(const BSGSIN& bsgs) 00071 : m_bsgs(bsgs) 00072 { } 00073 00074 template<class BSGSIN> 00075 void DadeInvariants<BSGSIN>::invariants(std::list<LinearFormList>& invariantList, unsigned int maximalDegree) const 00076 { 00077 const unsigned long n = m_bsgs.n; 00078 00079 std::map<unsigned long,OrbitSet<PERM,unsigned long> > orbits; 00080 boost::dynamic_bitset<> checked(n); 00081 unsigned long alpha = 0; 00082 while (true) { 00083 while (checked[alpha] && alpha < n) { 00084 ++alpha; 00085 } 00086 if (alpha >= n) 00087 break; 00088 00089 OrbitSet<PERM, unsigned long> orbit; 00090 orbit.orbit(alpha, m_bsgs.S, typename Transversal<PERM>::TrivialAction()); 00091 BOOST_FOREACH(const unsigned long& beta, std::make_pair(orbit.begin(), orbit.end())) { 00092 checked.set(beta, 1); 00093 } 00094 orbits.insert(std::make_pair(alpha, orbit)); 00095 } 00096 00097 typedef std::pair<unsigned long,OrbitSet<PERM,unsigned long> > pair_t; 00098 std::set<unsigned long>::const_iterator setIt; 00099 BOOST_FOREACH(const pair_t& orbit, orbits) { 00100 unsigned long l = 1; 00101 while (l < orbit.second.size()) { 00102 LinearForm form(n); 00103 setIt = orbit.second.begin(); 00104 for (unsigned int i = 0; i < orbit.second.size()-l; ++i) { 00105 form.set(*setIt, 1); 00106 ++setIt; 00107 } 00108 00109 OrbitSet<PERM, LinearForm> formOrbit; 00110 formOrbit.orbit(form, m_bsgs.S, LinearFormAction<PERM>()); 00111 LinearFormList list; 00112 BOOST_FOREACH(const LinearForm& lform, std::make_pair(formOrbit.begin(), formOrbit.end())) { 00113 list.add(lform); 00114 } 00115 00116 if (!maximalDegree || list.size() < maximalDegree) 00117 invariantList.push_back(list); 00118 l <<= 1; 00119 } 00120 } 00121 } 00122 00123 } 00124 00125 #endif // -- DADE_INVARIANTS_H_