33 #ifndef PRIMITIVITY_TEST_H_ 34 #define PRIMITIVITY_TEST_H_ 36 #include <permlib/prime_helper.h> 38 #include <boost/foreach.hpp> 39 #include <boost/utility.hpp> 54 template<
typename PERM>
64 template<
typename InputIterator>
65 PrimitivityTest(
const unsigned int n, InputIterator genBegin, InputIterator genEnd);
83 bool allBlocks(std::list<std::vector<dom_int> >* blocks,
bool findOnlyOneBlock =
false)
const;
91 const unsigned int m_n;
92 unsigned int m_primeLimit;
93 const std::list<typename PERM::ptr> m_generators;
95 bool fillTrivialBlock(std::list<std::vector<dom_int> >* block)
const;
97 static dom_int rep(dom_int kappa, std::vector<dom_int>& p);
99 bool merge(dom_int kappa, dom_int lambda, std::vector<dom_int>& c, std::vector<dom_int>& p, std::vector<dom_int>& q,
unsigned int& l)
const;
104 template<
typename PERM>
105 template<
typename InputIterator>
107 : m_n(n), m_primeLimit(m_n), m_generators(genBegin, genEnd)
110 if (m_n % (*p) == 0) {
111 m_primeLimit = m_n / (*p);
117 template<
typename PERM>
120 std::list<std::vector<dom_int> > blocks;
121 const bool is_primitive = allBlocks(&blocks,
true);
122 minimalBlock->clear();
123 minimalBlock->reserve(blocks.front().size());
124 std::copy(blocks.front().begin(), blocks.front().end(), std::back_inserter(*minimalBlock));
127 return allBlocks(0,
true);
131 template<
typename PERM>
133 std::vector<dom_int> alphas(2);
134 std::set<dom_int> workedAlphas;
137 for (dom_int a = 1; a < m_n; ++a) {
138 if (workedAlphas.count(a))
142 const unsigned int k = alphas.size();
143 unsigned int l = k - 1;
144 std::vector<dom_int> p(m_n);
145 std::vector<dom_int> q(m_n);
146 std::vector<dom_int> c(m_n);
148 for (
unsigned int i = 0; i < m_n; ++i) {
153 for (
unsigned int i = 0; i < k - 1; ++i) {
154 p[alphas[i+1]] = alphas[0];
159 for (
unsigned int i = 0; i < l; ++i) {
160 const dom_int gamma = q[i];
161 BOOST_FOREACH(
const typename PERM::ptr& x, m_generators) {
162 const dom_int delta = rep(gamma, p);
163 if (merge(x->at(gamma), x->at(delta), c, p, q, l)) {
169 for (
unsigned int i = 0; i < m_n; ++i)
172 if (c[rep(alphas[0], p)] < m_n) {
174 std::vector<dom_int> block;
175 block.reserve(c[rep(alphas[0], p)]);
176 for (
unsigned int i = 0; i < m_n; ++i) {
177 if (p[i] == p[alphas[0]]) {
180 workedAlphas.insert(i);
183 BOOST_ASSERT( block.size() == c[rep(alphas[0], p)] );
184 blocks->push_back(block);
186 if (findOnlyOneBlock)
195 if (!blocks->empty())
197 return fillTrivialBlock(blocks);
200 template<
typename PERM>
203 std::vector<dom_int> minimalBlock(m_n);
204 for (
unsigned int i = 0; i < m_n; ++i)
206 blocks->push_back(minimalBlock);
211 template<
typename PERM>
212 dom_int PrimitivityTest<PERM>::rep(dom_int kappa, std::vector<dom_int>& p) {
213 dom_int lambda = kappa;
214 dom_int rho = p[lambda];
215 while (rho != lambda) {
222 while (rho != lambda) {
231 template<
typename PERM>
232 bool PrimitivityTest<PERM>::merge(dom_int kappa, dom_int lambda, std::vector<dom_int>& c, std::vector<dom_int>& p, std::vector<dom_int>& q,
unsigned int& l)
const {
233 dom_int phi = rep(kappa, p);
234 dom_int psi = rep(lambda, p);
238 if (c[phi] >= c[psi]) {
247 if (c[mu] > m_primeLimit)
bool blockOfImprimitivity(std::vector< dom_int > *minimalBlock) const
Definition: primitivity_test.h:118
static const unsigned int * lastPrime()
iterator pointing after the last prime in list
Definition: prime_helper.h:75
static const unsigned int * firstPrime()
iterator pointing to the first prime in list
Definition: prime_helper.h:73
bool allBlocks(std::list< std::vector< dom_int > > *blocks, bool findOnlyOneBlock=false) const
Definition: primitivity_test.h:132
bool isPrimitive() const
Definition: primitivity_test.h:88
Tests a transitive group is availble for primitivity.
Definition: primitivity_test.h:55
PrimitivityTest(const unsigned int n, InputIterator genBegin, InputIterator genEnd)
Definition: primitivity_test.h:106
Definition: abstract_bsgs.h:49