permlib  0.2.9
Library for permutation computations
permlib_api.h
1 // ---------------------------------------------------------------------------
2 //
3 // This file is part of PermLib.
4 //
5 // Copyright (c) 2009-2011 Thomas Rehn <thomas@carmen76.de>
6 // All rights reserved.
7 //
8 // Redistribution and use in source and binary forms, with or without
9 // modification, are permitted provided that the following conditions
10 // are met:
11 // 1. Redistributions of source code must retain the above copyright
12 // notice, this list of conditions and the following disclaimer.
13 // 2. Redistributions in binary form must reproduce the above copyright
14 // notice, this list of conditions and the following disclaimer in the
15 // documentation and/or other materials provided with the distribution.
16 // 3. The name of the author may not be used to endorse or promote products
17 // derived from this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 //
30 // ---------------------------------------------------------------------------
31 
32 #ifndef PERMLIB_API_H
33 #define PERMLIB_API_H
34 
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>
47 
48 #include <boost/shared_ptr.hpp>
49 #include <boost/iterator/counting_iterator.hpp>
50 
51 namespace permlib {
52 
53 // ---------------------------------------------------------------------
54 // useful type definitions
55 //
56 
57 typedef Permutation PERMUTATION;
58 typedef SchreierTreeTransversal<PERMUTATION> TRANSVERSAL;
59 typedef BSGS<PERMUTATION,TRANSVERSAL> PermutationGroup;
60 typedef OrbitSet<PERMUTATION,unsigned long> OrbitAsSet;
61 
62 
63 // ---------------------------------------------------------------------
64 // BSGS construction
65 //
66 
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)));
71  return group;
72 }
73 
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)));
79  return group;
80 }
81 
82 
83 // ---------------------------------------------------------------------
84 // setwise stabilizer
85 //
86 
87 template<class InputIterator>
88 boost::shared_ptr<PermutationGroup> setStabilizer(const PermutationGroup& group, InputIterator begin, InputIterator end) {
89  if (begin == end)
90  return boost::shared_ptr<PermutationGroup>(new PermutationGroup(group));
91 
92  PermutationGroup copy(group);
93  // change the base so that is prefixed by the set
94  ConjugatingBaseChange<PERMUTATION,TRANSVERSAL,
95  RandomBaseTranspose<PERMUTATION,TRANSVERSAL> > baseChange(copy);
96  baseChange.change(copy, begin, end);
97 
98  // prepare search without DCM pruning
99  classic::SetStabilizerSearch<BSGS<PERMUTATION,TRANSVERSAL>, TRANSVERSAL> backtrackSearch(copy, 0);
100  backtrackSearch.construct(begin, end);
101 
102  // start the search
103  boost::shared_ptr<PermutationGroup> stabilizer(new PermutationGroup(copy.n));
104  backtrackSearch.search(*stabilizer);
105  return stabilizer;
106 }
107 
108 
109 // ---------------------------------------------------------------------
110 // set image
111 //
112 
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);
116  // change the base so that is prefixed by the set
117  ConjugatingBaseChange<PERMUTATION,TRANSVERSAL,
118  RandomBaseTranspose<PERMUTATION,TRANSVERSAL> > baseChange(copy);
119  baseChange.change(copy, begin, end);
120 
121  // prepare search without DCM pruning
122  classic::SetImageSearch<BSGS<PERMUTATION,TRANSVERSAL>, TRANSVERSAL> backtrackSearch(copy, 0);
123  backtrackSearch.construct(begin, end, begin2, end2);
124 
125  // start the search
126  return backtrackSearch.searchCosetRepresentative();
127 }
128 
129 
130 // ---------------------------------------------------------------------
131 // vector stabilizer
132 //
133 
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);
137  if (maxEntry == 0) {
138  BOOST_FOREACH(const unsigned int& v, vector) {
139  if (v > maxEntry)
140  maxEntry = v;
141  }
142  }
143  BOOST_ASSERT( maxEntry );
144  ++maxEntry;
145 
146  std::list<unsigned int> nonMaxEntries;
147  unsigned int i = 0;
148  BOOST_FOREACH(const unsigned int& v, vector) {
149  if (v < maxEntry-1)
150  nonMaxEntries.push_back(i);
151  ++i;
152  }
153 
154  PermutationGroup copy(group);
155  // change the base so that is prefixed by the set
156  ConjugatingBaseChange<PERMUTATION,TRANSVERSAL,
157  RandomBaseTranspose<PERMUTATION,TRANSVERSAL> > baseChange(copy);
158  baseChange.change(copy, nonMaxEntries.begin(), nonMaxEntries.end());
159 
160  // prepare search without DCM pruning
161  partition::VectorStabilizerSearch<BSGS<PERMUTATION,TRANSVERSAL>, TRANSVERSAL> backtrackSearch(copy, 0);
162  backtrackSearch.construct(vector.begin(), vector.end(), maxEntry);
163 
164  // start the search
165  boost::shared_ptr<PermutationGroup> stabilizer(new PermutationGroup(copy.n));
166  backtrackSearch.search(*stabilizer);
167  return stabilizer;
168 }
169 
170 
171 // ---------------------------------------------------------------------
172 // orbits
173 //
174 
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;
179 
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)) {
185  knownElement = true;
186  break;
187  }
188  }
189 
190  if (knownElement)
191  continue;
192 
193  ORBIT orbit(new OrbitSet<PERMUTATION,PDOMAIN>());
194  orbit->orbit(alpha, group.S, ACTION());
195  orbitList.push_back(orbit);
196  }
197 
198  return orbitList;
199 }
200 
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));
203 }
204 
205 // ---------------------------------------------------------------------
206 // smallest orbit element
207 //
208 
209 inline dset smallestSetImage(const PermutationGroup& group, const dset& set) {
210  OrbitLexMinSearch<PermutationGroup> orbLexMin(group);
211  return orbLexMin.lexMin(set);
212 }
213 
214 
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
220  )
221 {
222  // change the base so that is prefixed by the set
223  ConjugatingBaseChange<PERMUTATION,TRANSVERSAL,
224  RandomBaseTranspose<PERMUTATION,TRANSVERSAL> > baseChange(group);
225  baseChange.change(group, baseBegin, baseEnd);
226 
227  classic::LexSmallerImageSearch<PermutationGroup, TRANSVERSAL> backtrackSearch(group, 0);
228  backtrackSearch.construct(zerosBegin, zerosEnd, onesBegin, onesEnd);
229 
230  // start the search
231  typename PERMUTATION::ptr g = backtrackSearch.searchCosetRepresentative();
232  if (g) {
233  return true;
234  }
235  return false;
236 }
237 
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
243  )
244 {
245  PermutationGroup copy(group);
246  return isNotLexMinSet(copy, baseBegin, baseEnd, zerosBegin, zerosEnd, onesBegin, onesEnd);
247 }
248 
249 
250 } // namespace permlib
251 
252 
253 #endif // PERMLIB_API_H
254 
boost::shared_ptr< Permutation > ptr
boost shared_ptr of this class
Definition: permutation.h:64
Definition: abstract_bsgs.h:49