permlib  0.2.9
Library for permutation computations
conjugating_base_change.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 CONJUGATINGBASECHANGE_H_
34 #define CONJUGATINGBASECHANGE_H_
35 
36 #include <boost/foreach.hpp>
37 #include <boost/scoped_ptr.hpp>
38 #include <boost/cstdint.hpp>
39 
40 #include <permlib/change/base_change.h>
41 
42 namespace permlib {
43 
44 template<class PERM>
46 
47 template<class PERM,class TRANS>
48 struct BSGS;
49 
51 template<class PERM, class TRANS, class BASETRANSPOSE>
52 class ConjugatingBaseChange : public BaseChange<PERM,TRANS> {
53 public:
56 
58  template <class InputIterator>
59  unsigned int change(BSGS<PERM,TRANS> &bsgs, InputIterator baseBegin, InputIterator baseEnd, bool skipRedundant = false) const;
60 
62  template <class InputIterator>
63  unsigned int change(SymmetricGroup<PERM> &bsgs, InputIterator baseBegin, InputIterator baseEnd, bool skipRedundant = false) const;
64 };
65 
66 template<class PERM, class TRANS, class BASETRANSPOSE>
68  : BaseChange<PERM,TRANS>()
69 { }
70 
71 template<class PERM, class TRANS, class BASETRANSPOSE>
72 template<class InputIterator>
73 unsigned int ConjugatingBaseChange<PERM,TRANS,BASETRANSPOSE>::change(BSGS<PERM,TRANS> &bsgs, InputIterator baseBegin, InputIterator baseEnd, bool skipRedundant) const {
74  if (baseBegin == baseEnd)
75  return 0;
76 
77  const boost::uint64_t origOrder __attribute__((unused)) = bsgs.order();
78  BASETRANSPOSE trans;
79  PERM c(bsgs.n);
80  PERM cInv(bsgs.n);
82  bool touchedC = false;
83 
84  unsigned int baseTargetPos = 0;
85  while (baseBegin != baseEnd && baseTargetPos < bsgs.B.size()) {
86  const unsigned long alpha = cInv.at(*baseBegin);
87  const unsigned long beta = bsgs.B[baseTargetPos];
88  const bool redundant = skipRedundant && this->isRedundant(bsgs, baseTargetPos, alpha);
89 
90  if (!redundant && beta != alpha) {
91  boost::scoped_ptr<PERM> r(bsgs.U[baseTargetPos].at(alpha));
92  if (r) {
93  c ^= *r;
94  cInv = ~c;
95  touchedC = true;
96  } else {
97  unsigned int pos = bsgs.insertRedundantBasePoint(alpha, baseTargetPos);
98  for (; pos > baseTargetPos; --pos) {
99  trans.transpose(bsgs, pos-1);
101  }
102  }
103  }
104  if (!redundant)
105  ++baseTargetPos;
106  ++baseBegin;
107  }
108 
109  // insert remaining base points
110  while (!skipRedundant && baseBegin != baseEnd) {
111  const unsigned long alpha = cInv.at(*baseBegin);
112  bsgs.insertRedundantBasePoint(alpha, baseTargetPos);
113 
114  ++baseBegin;
115  ++baseTargetPos;
116  }
117 
118  if (touchedC) {
119  // correct generators by conjugation
120  BOOST_FOREACH(typename PERM::ptr& g, bsgs.S) {
121  *g ^= cInv;
122  *g *= c;
123  g->flush();
124  }
125 
126  // correct base points
127  BOOST_FOREACH(dom_int& beta, bsgs.B) {
128  beta = c.at(beta);
129  }
130  }
131 
132  // always strip redundant base points from the end of the new base
133  bsgs.stripRedundantBasePoints(baseTargetPos);
135 
136  if (touchedC) {
137  for (unsigned int i=0; i<bsgs.U.size(); ++i) {
138  bsgs.U[i].permute(c, cInv);
139  }
140  }
141 
142  BOOST_ASSERT(bsgs.B.size() == bsgs.U.size());
143  BOOST_ASSERT(origOrder == bsgs.order());
144 
145  return baseTargetPos;
146 }
147 
148 template<class PERM, class TRANS, class BASETRANSPOSE>
149 template<class InputIterator>
150 unsigned int ConjugatingBaseChange<PERM,TRANS,BASETRANSPOSE>::change(SymmetricGroup<PERM> &bsgs, InputIterator baseBegin, InputIterator baseEnd, bool skipRedundant) const {
151  unsigned int basePos = 0;
152  while (baseBegin != baseEnd) {
153  //std::cout << "base prefix " << *baseBegin << std::endl;
154  for (unsigned int i = basePos; i < bsgs.B.size(); ++i) {
155  if (bsgs.B[i] == *baseBegin) {
156  std::swap(bsgs.B[i], bsgs.B[basePos]);
157  //std::cout << " swap " << i << " and " << basePos << std::endl;
158  break;
159  }
160  }
161  ++basePos;
162  ++baseBegin;
163  }
164  return basePos;
165 }
166 
167 }
168 
169 #endif // -- CONJUGATINGBASECHANGE_H_
dom_int n
degree of group
Definition: bsgs_core.h:61
unsigned int insertRedundantBasePoint(unsigned int beta, unsigned int minPos=0)
inserts a redundant base beta
Definition: bsgs.h:421
abstract base class for base change algorithms
Definition: base_change.h:46
base change by conjugation and, if necessary, transpositions
Definition: conjugating_base_change.h:52
core data of a base and strong generating set (BSGS)
Definition: bsgs_core.h:42
representation of a symmetric group
Definition: conjugating_base_change.h:45
Integer order() const
order of the group
Definition: bsgs.h:406
void stripRedundantBasePoints(int minPos=0)
strips redundant base points from the end to the minPos-th base element
Definition: bsgs.h:436
std::vector< dom_int > B
base
Definition: bsgs_core.h:55
unsigned int change(BSGS< PERM, TRANS > &bsgs, InputIterator baseBegin, InputIterator baseEnd, bool skipRedundant=false) const
changes base of bsgs so that it starts with the sequence given by baseBegin to baseEnd ...
Definition: conjugating_base_change.h:73
ConjugatingBaseChange(const BSGSCore< PERM, TRANS > &)
constructor
Definition: conjugating_base_change.h:67
unsigned int m_statScheierGeneratorsConsidered
nuber of Schreier generators considered in transposition since construction
Definition: base_change.h:55
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
PERMlist S
strong generating set
Definition: bsgs_core.h:57
Definition: abstract_bsgs.h:49