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>
57typedef Permutation PERMUTATION;
58typedef SchreierTreeTransversal<PERMUTATION> TRANSVERSAL;
59typedef BSGS<PERMUTATION,TRANSVERSAL> PermutationGroup;
60typedef OrbitSet<PERMUTATION,unsigned long> OrbitAsSet;
67template<
class InputIterator>
68boost::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)));
74template<
class InputIteratorGen,
class InputIteratorBase>
75boost::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)));
87template<
class InputIterator>
88boost::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);
113template<
class InputIterator>
114boost::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();
134template<
class InputIterator>
135boost::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);
175template<
typename PDOMAIN,
typename ACTION,
typename InputIterator>
176std::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);
201inline 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));
209inline dset smallestSetImage(
const PermutationGroup& group,
const dset& set) {
210 OrbitLexMinSearch<PermutationGroup> orbLexMin(group);
211 return orbLexMin.lexMin(set);
215template<
class InputIteratorB,
class InputIteratorZ,
class InputIteratorO>
216inline 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);
238template<
class InputIteratorB,
class InputIteratorZ,
class InputIteratorO>
239inline 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);
boost::shared_ptr< Permutation > ptr
boost shared_ptr of this class
Definition permutation.h:64