permlib  0.2.9
Library for permutation computations
base_construction.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 
33 #ifndef BASECONSTRUCTION_H
34 #define BASECONSTRUCTION_H
35 
36 #include <map>
37 #include <algorithm>
38 
39 #include <permlib/predicate/pointwise_stabilizer_predicate.h>
40 #include <permlib/predicate/identity_predicate.h>
41 
42 namespace permlib {
43 
45 template <class PERM, class TRANS>
47 public:
49 
52  explicit BaseConstruction(dom_int n);
53 protected:
55  dom_int m_n;
56 
58 
66  template <class ForwardIterator, class InputIterator>
67  void setup(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd, BSGS<PERM, TRANS> &bsgs, std::vector<std::list<typename PERM::ptr> > &S) const;
68 
70  void mergeGenerators(std::vector<std::list<typename PERM::ptr> >& S, BSGS<PERM,TRANS>& ret) const;
71 
73  static const unsigned long *empty;
74 };
75 
76 //
77 // ---- IMPLEMENTATION
78 //
79 
80 template <class PERM, class TRANS>
81 const unsigned long *BaseConstruction<PERM, TRANS>::empty = static_cast<unsigned long*>(0);
82 
83 
84 template <class PERM, class TRANS>
86  : m_n(n)
87 { }
88 
89 template <class PERM, class TRANS>
90 template <class ForwardIterator, class InputIterator>
91 void BaseConstruction<PERM,TRANS>::setup(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd, BSGS<PERM, TRANS> &bsgs, std::vector<std::list<typename PERM::ptr> > &S) const
92 {
93  std::vector<dom_int> &B = bsgs.B;
94  std::vector<TRANS> &U = bsgs.U;
95 
96  std::list<typename PERM::ptr> nonIdentityGenerators;
97  std::remove_copy_if(generatorsBegin, generatorsEnd, std::back_inserter(nonIdentityGenerators), IdentityPredicate<PERM>());
98 
99  B.insert(B.begin(), prescribedBaseBegin, prescribedBaseEnd);
100  // extend base so that no group element fixes all base elements
101  dom_int beta = m_n + 1;
102  PointwiseStabilizerPredicate<PERM> stab_k(B.begin(), B.end());
103  BOOST_FOREACH(const typename PERM::ptr &gen, nonIdentityGenerators) {
104  if (stab_k(gen)) {
105  if (bsgs.chooseBaseElement(*gen, beta)) {
106  B.push_back(beta);
107  stab_k = PointwiseStabilizerPredicate<PERM>(B.begin(), B.end());
108  }
109  }
110  }
111 
112  if (B.empty()) {
113  B.push_back(0);
114  U.push_back(TRANS(m_n));
115  // the trivial group has an empty generator list
116  std::list<typename PERM::ptr> S_0;
117  S.push_back(S_0);
118  U[0].orbit(B[0], S_0);
119  return;
120  }
121  S.reserve(B.size());
122 
123  // pre-compute transversals and fundamental orbits for the current base
124  unsigned int i = 0;
125  std::vector<dom_int>::iterator Bit;
126  for (Bit = B.begin(); Bit != B.end(); ++Bit) {
127  std::list<typename PERM::ptr> S_i;
128  std::copy_if(nonIdentityGenerators.begin(), nonIdentityGenerators.end(),
129  std::back_inserter(S_i), PointwiseStabilizerPredicate<PERM>(B.begin(), Bit));
130 
131  U.push_back(TRANS(m_n));
132  S.push_back(S_i);
133 
134  bsgs.orbit(i, S_i);
135 
136  ++i;
137  }
138 }
139 
140 template <class PERM, class TRANS>
141 void BaseConstruction<PERM,TRANS>::mergeGenerators(std::vector<std::list<typename PERM::ptr> >& S, BSGS<PERM,TRANS>& ret) const {
142  std::map<PERM*,typename PERM::ptr> generatorMap;
143  // merge all generators into one list
144  BOOST_FOREACH(std::list<typename PERM::ptr> &S_j, S) {
145  BOOST_FOREACH(typename PERM::ptr &gen, S_j) {
146  bool found = false;
147  BOOST_FOREACH(const typename PERM::ptr& genS, ret.S) {
148  if (*genS == *gen) {
149  found = true;
150  generatorMap.insert(std::make_pair(gen.get(), genS));
151  break;
152  }
153  }
154  if (!found) {
155  ret.S.push_back(gen);
156  generatorMap.insert(std::make_pair(gen.get(), gen));
157  }
158  }
159  }
160 
161  BOOST_FOREACH(TRANS& U_i, ret.U) {
162  U_i.updateGenerators(generatorMap);
163  }
164 }
165 
166 }
167 
168 #endif // -- BASECONSTRUCTION_H
BaseConstruction(dom_int n)
constructor
Definition: base_construction.h:85
bool chooseBaseElement(const PERM &h, dom_int &beta) const
tries to find a new base element
Definition: bsgs.h:289
predicate matching a permutation if it stabilizes a given list of points pointwise ...
Definition: pointwise_stabilizer_predicate.h:42
void mergeGenerators(std::vector< std::list< typename PERM::ptr > > &S, BSGS< PERM, TRANS > &ret) const
merges all strong generators in S into a single strong generating set ret.S
Definition: base_construction.h:141
dom_int m_n
cardinality of the set the group is acting on
Definition: base_construction.h:55
std::vector< dom_int > B
base
Definition: bsgs_core.h:55
base class for BSGS construction algorithms
Definition: base_construction.h:46
static const unsigned long * empty
auxilliary element marking an empty iterator
Definition: base_construction.h:73
predicate matching a permutation if it stabilizes a given list of points pointwise ...
Definition: identity_predicate.h:42
Represents a base and strong generating set (BSGS)
Definition: bsgs.h:58
std::vector< TRANS > U
transversals along the stabilizer chain
Definition: bsgs_core.h:59
void orbit(unsigned int j, const PERMlist &generators)
re-computes the j-th fundamental orbit with the given orbit generators
Definition: bsgs.h:300
void setup(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd, BSGS< PERM, TRANS > &bsgs, std::vector< std::list< typename PERM::ptr > > &S) const
initializes BSGS object
Definition: base_construction.h:91
PERMlist S
strong generating set
Definition: bsgs_core.h:57
Definition: abstract_bsgs.h:49