permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
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
42namespace permlib {
43
45template <class PERM, class TRANS>
47public:
49
52 explicit BaseConstruction(dom_int n);
53protected:
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
80template <class PERM, class TRANS>
81const unsigned long *BaseConstruction<PERM, TRANS>::empty = static_cast<unsigned long*>(0);
82
83
84template <class PERM, class TRANS>
86 : m_n(n)
87{ }
88
89template <class PERM, class TRANS>
90template <class ForwardIterator, class InputIterator>
91void 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
140template <class PERM, class TRANS>
141void 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
base class for BSGS construction algorithms
Definition: base_construction.h:46
BaseConstruction(dom_int n)
constructor
Definition: base_construction.h:85
dom_int m_n
cardinality of the set the group is acting on
Definition: base_construction.h:55
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
static const unsigned long * empty
auxilliary element marking an empty iterator
Definition: base_construction.h:73
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
predicate matching a permutation if it stabilizes a given list of points pointwise
Definition: identity_predicate.h:42
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: bsgs.h:89
void orbit(unsigned int j, const PERMlist &generators)
re-computes the j-th fundamental orbit with the given orbit generators
Definition: bsgs.h:301
bool chooseBaseElement(const PERM &h, dom_int &beta) const
tries to find a new base element
Definition: bsgs.h:290