35 #include <permlib/common.h> 36 #include <permlib/permutation.h> 37 #include <permlib/bsgs.h> 38 #include <permlib/transversal/schreier_tree_transversal.h> 39 #include <permlib/transversal/orbit_set.h> 40 #include <permlib/construct/schreier_sims_construction.h> 41 #include <permlib/change/conjugating_base_change.h> 42 #include <permlib/search/partition/vector_stabilizer_search.h> 43 #include <permlib/search/classic/set_stabilizer_search.h> 44 #include <permlib/search/classic/set_image_search.h> 45 #include <permlib/search/classic/lex_smaller_image_search.h> 46 #include <permlib/search/orbit_lex_min_search.h> 48 #include <boost/shared_ptr.hpp> 49 #include <boost/iterator/counting_iterator.hpp> 57 typedef Permutation PERMUTATION;
58 typedef SchreierTreeTransversal<PERMUTATION> TRANSVERSAL;
59 typedef BSGS<PERMUTATION,TRANSVERSAL> PermutationGroup;
60 typedef OrbitSet<PERMUTATION,unsigned long> OrbitAsSet;
67 template<
class InputIterator>
68 boost::shared_ptr<PermutationGroup> construct(
unsigned long n, InputIterator begin, InputIterator end) {
69 SchreierSimsConstruction<PERMUTATION, TRANSVERSAL> schreierSims(n);
70 boost::shared_ptr<PermutationGroup> group(
new PermutationGroup(schreierSims.construct(begin, end)));
74 template<
class InputIteratorGen,
class InputIteratorBase>
75 boost::shared_ptr<PermutationGroup> construct(
unsigned long n, InputIteratorGen beginGen, InputIteratorGen endGen,
76 InputIteratorBase beginBase, InputIteratorBase endBase) {
77 SchreierSimsConstruction<PERMUTATION, TRANSVERSAL> schreierSims(n);
78 boost::shared_ptr<PermutationGroup> group(
new PermutationGroup(schreierSims.construct(beginGen, endGen, beginBase, endBase)));
87 template<
class InputIterator>
88 boost::shared_ptr<PermutationGroup> setStabilizer(
const PermutationGroup& group, InputIterator begin, InputIterator end) {
90 return boost::shared_ptr<PermutationGroup>(
new PermutationGroup(group));
92 PermutationGroup copy(group);
94 ConjugatingBaseChange<PERMUTATION,TRANSVERSAL,
95 RandomBaseTranspose<PERMUTATION,TRANSVERSAL> > baseChange(copy);
96 baseChange.change(copy, begin, end);
99 classic::SetStabilizerSearch<BSGS<PERMUTATION,TRANSVERSAL>, TRANSVERSAL> backtrackSearch(copy, 0);
100 backtrackSearch.construct(begin, end);
103 boost::shared_ptr<PermutationGroup> stabilizer(
new PermutationGroup(copy.n));
104 backtrackSearch.search(*stabilizer);
113 template<
class InputIterator>
114 boost::shared_ptr<Permutation> setImage(
const PermutationGroup& group, InputIterator begin, InputIterator end, InputIterator begin2, InputIterator end2) {
115 PermutationGroup copy(group);
117 ConjugatingBaseChange<PERMUTATION,TRANSVERSAL,
118 RandomBaseTranspose<PERMUTATION,TRANSVERSAL> > baseChange(copy);
119 baseChange.change(copy, begin, end);
122 classic::SetImageSearch<BSGS<PERMUTATION,TRANSVERSAL>, TRANSVERSAL> backtrackSearch(copy, 0);
123 backtrackSearch.construct(begin, end, begin2, end2);
126 return backtrackSearch.searchCosetRepresentative();
134 template<
class InputIterator>
135 boost::shared_ptr<PermutationGroup> vectorStabilizer(
const PermutationGroup& group, InputIterator begin, InputIterator end,
unsigned int maxEntry = 0) {
136 std::vector<unsigned int> vector(begin, end);
138 BOOST_FOREACH(
const unsigned int& v, vector) {
143 BOOST_ASSERT( maxEntry );
146 std::list<unsigned int> nonMaxEntries;
148 BOOST_FOREACH(
const unsigned int& v, vector) {
150 nonMaxEntries.push_back(i);
154 PermutationGroup copy(group);
156 ConjugatingBaseChange<PERMUTATION,TRANSVERSAL,
157 RandomBaseTranspose<PERMUTATION,TRANSVERSAL> > baseChange(copy);
158 baseChange.change(copy, nonMaxEntries.begin(), nonMaxEntries.end());
161 partition::VectorStabilizerSearch<BSGS<PERMUTATION,TRANSVERSAL>, TRANSVERSAL> backtrackSearch(copy, 0);
162 backtrackSearch.construct(vector.begin(), vector.end(), maxEntry);
165 boost::shared_ptr<PermutationGroup> stabilizer(
new PermutationGroup(copy.n));
166 backtrackSearch.search(*stabilizer);
175 template<
typename PDOMAIN,
typename ACTION,
typename InputIterator>
176 std::list<boost::shared_ptr<OrbitSet<PERMUTATION,PDOMAIN> > > orbits(
const PermutationGroup& group, InputIterator begin, InputIterator end) {
177 typedef boost::shared_ptr<OrbitSet<PERMUTATION,PDOMAIN> > ORBIT;
178 std::list<ORBIT> orbitList;
180 for (; begin != end; ++begin) {
181 const PDOMAIN& alpha = *begin;
182 bool knownElement =
false;
183 BOOST_FOREACH(
const ORBIT& orb, orbitList) {
184 if (orb->contains(alpha)) {
193 ORBIT orbit(
new OrbitSet<PERMUTATION,PDOMAIN>());
194 orbit->orbit(alpha, group.S, ACTION());
195 orbitList.push_back(orbit);
201 inline std::list<boost::shared_ptr<OrbitAsSet> > orbits(
const PermutationGroup& group) {
202 return orbits<unsigned long, Transversal<PERMUTATION>::TrivialAction>(group, boost::counting_iterator<unsigned long>(0), boost::counting_iterator<unsigned long>(group.n));
209 inline dset smallestSetImage(
const PermutationGroup& group,
const dset&
set) {
210 OrbitLexMinSearch<PermutationGroup> orbLexMin(group);
211 return orbLexMin.lexMin(
set);
215 template<
class InputIteratorB,
class InputIteratorZ,
class InputIteratorO>
216 inline bool isNotLexMinSet(PermutationGroup& group,
217 InputIteratorB baseBegin, InputIteratorB baseEnd,
218 InputIteratorZ zerosBegin, InputIteratorZ zerosEnd,
219 InputIteratorO onesBegin, InputIteratorO onesEnd
223 ConjugatingBaseChange<PERMUTATION,TRANSVERSAL,
224 RandomBaseTranspose<PERMUTATION,TRANSVERSAL> > baseChange(group);
225 baseChange.change(group, baseBegin, baseEnd);
227 classic::LexSmallerImageSearch<PermutationGroup, TRANSVERSAL> backtrackSearch(group, 0);
228 backtrackSearch.construct(zerosBegin, zerosEnd, onesBegin, onesEnd);
238 template<
class InputIteratorB,
class InputIteratorZ,
class InputIteratorO>
239 inline bool isNotLexMinSet(
const PermutationGroup& group,
240 InputIteratorB baseBegin, InputIteratorB baseEnd,
241 InputIteratorZ zerosBegin, InputIteratorZ zerosEnd,
242 InputIteratorO onesBegin, InputIteratorO onesEnd
245 PermutationGroup copy(group);
246 return isNotLexMinSet(copy, baseBegin, baseEnd, zerosBegin, zerosEnd, onesBegin, onesEnd);
253 #endif // PERMLIB_API_H boost::shared_ptr< Permutation > ptr
boost shared_ptr of this class
Definition: permutation.h:64
Definition: abstract_bsgs.h:49