permlib  0.2.9
Library for permutation computations
base_transpose.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 BASETRANSPOSE_H_
34 #define BASETRANSPOSE_H_
35 
36 #include <permlib/predicate/pointwise_stabilizer_predicate.h>
37 #include <permlib/generator/generator.h>
38 
39 #include <boost/scoped_ptr.hpp>
40 #include <boost/iterator/indirect_iterator.hpp>
41 
42 namespace permlib {
43 
45 
48 template<class PERM, class TRANS>
50 public:
52  BaseTranspose();
54  virtual ~BaseTranspose() {}
55 
57 
61  void transpose(BSGS<PERM,TRANS> &bsgs, unsigned int i) const;
62 
64  mutable unsigned int m_statScheierGeneratorsConsidered;
66  mutable unsigned int m_statNewGenerators;
67 protected:
68  typedef std::list<typename PERM::ptr> PERMlist;
69 
71 
77  virtual Generator<PERM>* setupGenerator(BSGS<PERM,TRANS> &bsgs, unsigned int i, const PERMlist &S_i, const TRANS &U_i) const = 0;
78 };
79 
80 //
81 // ---- IMPLEMENTATION
82 //
83 
84 template<class PERM, class TRANS>
86  : m_statScheierGeneratorsConsidered(0), m_statNewGenerators(0)
87 { }
88 
89 template<class PERM, class TRANS>
90 void BaseTranspose<PERM,TRANS>::transpose(BSGS<PERM,TRANS> &bsgs, unsigned int i) const {
91  std::vector<dom_int> &B = bsgs.B;
92  std::vector<TRANS> &U = bsgs.U;
93 
94  if (i+1 >= B.size())
95  // illegal transpose index
96  return;
97 
98  PERMlist S_i;
99  std::copy_if(bsgs.S.begin(), bsgs.S.end(), std::back_inserter(S_i), PointwiseStabilizerPredicate<PERM>(B.begin(), B.begin() + i));
100 
101  std::swap(B[i], B[i+1]);
102 
103  PERMlist S_i1;
104  std::copy_if(bsgs.S.begin(), bsgs.S.end(), std::back_inserter(S_i1), PointwiseStabilizerPredicate<PERM>(B.begin(), B.begin() + (i+1)));
105 
106  unsigned int targetTransversalSize = U[i+1].size() * U[i].size();
107 
108  // new transversal
109  TRANS U_i(U[i].n());
110  U_i.orbit(B[i], S_i);
111  targetTransversalSize /= U_i.size();
112 
113  m_statScheierGeneratorsConsidered = 0;
114  m_statNewGenerators = 0;
115  TRANS U_i1(U[i+1].n());
116  U_i1.orbit(B[i+1], S_i1);
117  boost::scoped_ptr<Generator<PERM> > generator(setupGenerator(bsgs, i, S_i, U_i));
118  BOOST_ASSERT(generator != 0);
119 
120  while (U_i1.size() < targetTransversalSize) {
121  bool newGeneratorFound = false;
122  while (generator->hasNext()) {
123  PERM g = generator->next();
124  ++m_statScheierGeneratorsConsidered;
125  boost::indirect_iterator<typename PERMlist::iterator> sBegin(S_i1.begin()), sEnd(S_i1.end());
126  if (!U_i1.contains(g / B[i+1]) && std::find(sBegin, sEnd, g) == sEnd) {
127  g.flush();
128  boost::shared_ptr<PERM> gen(new PERM(g));
129  S_i1.push_front(gen);
130  ++m_statNewGenerators;
131  U_i1.orbitUpdate(B[i+1], S_i1, gen);
132  newGeneratorFound = true;
133  break;
134  }
135  }
136  if (!newGeneratorFound)
137  // we have exhausted all available generators, and we won't find any new ones in the loop
138  break;
139  }
140  BOOST_ASSERT(U_i1.size() >= targetTransversalSize);
141 
142  bsgs.S.insert(bsgs.S.end(), S_i1.begin(), boost::next(S_i1.begin(), m_statNewGenerators));
143  U[i] = U_i;
144  U[i+1] = U_i1;
145 }
146 
147 }
148 
149 #endif // -- BASETRANSPOSE_H_
virtual Generator< PERM > * setupGenerator(BSGS< PERM, TRANS > &bsgs, unsigned int i, const PERMlist &S_i, const TRANS &U_i) const =0
initializes the specific Schreier Generator that is used for the BaseTranpose implementation ...
BaseTranspose()
constructor
Definition: base_transpose.h:85
unsigned int m_statScheierGeneratorsConsidered
number of Schreier generators that have been considered during the last transpose call ...
Definition: base_transpose.h:64
void transpose(BSGS< PERM, TRANS > &bsgs, unsigned int i) const
performs a base transposition on bsgs between bsgs.B[i] and bsgs.B[i+1]
Definition: base_transpose.h:90
interface for group element generators
Definition: generator.h:40
predicate matching a permutation if it stabilizes a given list of points pointwise ...
Definition: pointwise_stabilizer_predicate.h:42
std::vector< dom_int > B
base
Definition: bsgs_core.h:55
unsigned int m_statNewGenerators
number of new strong generators that have been added during the last transpose call ...
Definition: base_transpose.h:66
abstract base class for base transposition
Definition: base_transpose.h:49
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
virtual ~BaseTranspose()
virtual destructor
Definition: base_transpose.h:54
PERMlist S
strong generating set
Definition: bsgs_core.h:57
Definition: abstract_bsgs.h:49