permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
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
42namespace permlib {
43
44template<class PERM>
45struct SymmetricGroup;
46
47template<class PERM,class TRANS>
48struct BSGS;
49
51template<class PERM, class TRANS, class BASETRANSPOSE>
52class ConjugatingBaseChange : public BaseChange<PERM,TRANS> {
53public:
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
66template<class PERM, class TRANS, class BASETRANSPOSE>
70
71template<class PERM, class TRANS, class BASETRANSPOSE>
72template<class InputIterator>
73unsigned 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);
134 BaseChange<PERM,TRANS>::m_statScheierGeneratorsConsidered += trans.m_statScheierGeneratorsConsidered;
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
148template<class PERM, class TRANS, class BASETRANSPOSE>
149template<class InputIterator>
150unsigned 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_
unsigned int m_statScheierGeneratorsConsidered
nuber of Schreier generators considered in transposition since construction
Definition base_change.h:55
bool isRedundant(const BSGSCore< PERM, TRANS > &bsgs, unsigned int baseTargetPos, unsigned long alpha) const
checks if insertion of a base point at given position is redundant
Definition base_change.h:67
unsigned int m_statTranspositions
nuber of base transpositions needed since construction
Definition base_change.h:52
BaseChange()
constructor
Definition base_change.h:49
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 change(SymmetricGroup< PERM > &bsgs, InputIterator baseBegin, InputIterator baseEnd, bool skipRedundant=false) const
changes base of symmetric group so that it starts with the sequence given by baseBegin to baseEnd
Definition conjugating_base_change.h:150
core data of a base and strong generating set (BSGS)
Definition bsgs_core.h:42
dom_int n
degree of group
Definition bsgs_core.h:61
std::vector< TRANS > U
transversals along the stabilizer chain
Definition bsgs_core.h:59
std::vector< dom_int > B
base
Definition bsgs_core.h:55
PERMlist S
strong generating set
Definition bsgs_core.h:57
Represents a base and strong generating set (BSGS)
Definition bsgs.h:89
unsigned int insertRedundantBasePoint(unsigned int beta, unsigned int minPos=0)
inserts a redundant base beta
Definition bsgs.h:422
void stripRedundantBasePoints(int minPos=0)
strips redundant base points from the end to the minPos-th base element
Definition bsgs.h:437
Integer order() const
order of the group
Definition bsgs.h:407
representation of a symmetric group
Definition symmetric_group.h:52