permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
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#include <boost/next_prior.hpp>
42
43namespace permlib {
44
46
49template<class PERM, class TRANS>
51public:
55 virtual ~BaseTranspose() {}
56
58
62 void transpose(BSGS<PERM,TRANS> &bsgs, unsigned int i) const;
63
67 mutable unsigned int m_statNewGenerators;
68protected:
69 typedef std::list<typename PERM::ptr> PERMlist;
70
72
78 virtual Generator<PERM>* setupGenerator(BSGS<PERM,TRANS> &bsgs, unsigned int i, const PERMlist &S_i, const TRANS &U_i) const = 0;
79};
80
81//
82// ---- IMPLEMENTATION
83//
84
85template<class PERM, class TRANS>
87 : m_statScheierGeneratorsConsidered(0), m_statNewGenerators(0)
88{ }
89
90template<class PERM, class TRANS>
91void BaseTranspose<PERM,TRANS>::transpose(BSGS<PERM,TRANS> &bsgs, unsigned int i) const {
92 std::vector<dom_int> &B = bsgs.B;
93 std::vector<TRANS> &U = bsgs.U;
94
95 if (i+1 >= B.size())
96 // illegal transpose index
97 return;
98
99 PERMlist S_i;
100 std::copy_if(bsgs.S.begin(), bsgs.S.end(), std::back_inserter(S_i), PointwiseStabilizerPredicate<PERM>(B.begin(), B.begin() + i));
101
102 std::swap(B[i], B[i+1]);
103
104 PERMlist S_i1;
105 std::copy_if(bsgs.S.begin(), bsgs.S.end(), std::back_inserter(S_i1), PointwiseStabilizerPredicate<PERM>(B.begin(), B.begin() + (i+1)));
106
107 unsigned int targetTransversalSize = U[i+1].size() * U[i].size();
108
109 // new transversal
110 TRANS U_i(U[i].n());
111 U_i.orbit(B[i], S_i);
112 targetTransversalSize /= U_i.size();
113
114 m_statScheierGeneratorsConsidered = 0;
115 m_statNewGenerators = 0;
116 TRANS U_i1(U[i+1].n());
117 U_i1.orbit(B[i+1], S_i1);
118 boost::scoped_ptr<Generator<PERM> > generator(setupGenerator(bsgs, i, S_i, U_i));
119 BOOST_ASSERT(generator != 0);
120
121 while (U_i1.size() < targetTransversalSize) {
122 bool newGeneratorFound = false;
123 while (generator->hasNext()) {
124 PERM g = generator->next();
125 ++m_statScheierGeneratorsConsidered;
126 boost::indirect_iterator<typename PERMlist::iterator> sBegin(S_i1.begin()), sEnd(S_i1.end());
127 if (!U_i1.contains(g / B[i+1]) && std::find(sBegin, sEnd, g) == sEnd) {
128 g.flush();
129 boost::shared_ptr<PERM> gen(new PERM(g));
130 S_i1.push_front(gen);
131 ++m_statNewGenerators;
132 U_i1.orbitUpdate(B[i+1], S_i1, gen);
133 newGeneratorFound = true;
134 break;
135 }
136 }
137 if (!newGeneratorFound)
138 // we have exhausted all available generators, and we won't find any new ones in the loop
139 break;
140 }
141 BOOST_ASSERT(U_i1.size() >= targetTransversalSize);
142
143 bsgs.S.insert(bsgs.S.end(), S_i1.begin(), boost::next(S_i1.begin(), m_statNewGenerators));
144 U[i] = U_i;
145 U[i+1] = U_i1;
146}
147
148}
149
150#endif // -- BASETRANSPOSE_H_
abstract base class for base transposition
Definition base_transpose.h:50
unsigned int m_statScheierGeneratorsConsidered
number of Schreier generators that have been considered during the last transpose call
Definition base_transpose.h:65
unsigned int m_statNewGenerators
number of new strong generators that have been added during the last transpose call
Definition base_transpose.h:67
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:91
BaseTranspose()
constructor
Definition base_transpose.h:86
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
virtual ~BaseTranspose()
virtual destructor
Definition base_transpose.h:55
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
OutputIterator copy_if(InputIterator begin, InputIterator end, OutputIterator destBegin, Predicate p)
copies elements of (begin to end) to destBegin if they match the given predicate
Definition common.h:49
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 redundant_base_point_insertion_strategy.h:39