permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
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
51namespace permlib {
52
53// ---------------------------------------------------------------------
54// useful type definitions
55//
56
57typedef Permutation PERMUTATION;
58typedef SchreierTreeTransversal<PERMUTATION> TRANSVERSAL;
59typedef BSGS<PERMUTATION,TRANSVERSAL> PermutationGroup;
60typedef OrbitSet<PERMUTATION,unsigned long> OrbitAsSet;
61
62
63// ---------------------------------------------------------------------
64// BSGS construction
65//
66
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)));
71 return group;
72}
73
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)));
79 return group;
80}
81
82
83// ---------------------------------------------------------------------
84// setwise stabilizer
85//
86
87template<class InputIterator>
88boost::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
113template<class InputIterator>
114boost::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
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);
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
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;
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
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));
203}
204
205// ---------------------------------------------------------------------
206// smallest orbit element
207//
208
209inline dset smallestSetImage(const PermutationGroup& group, const dset& set) {
210 OrbitLexMinSearch<PermutationGroup> orbLexMin(group);
211 return orbLexMin.lexMin(set);
212}
213
214
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
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
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
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