permlib  0.2.9
Library for permutation computations
primitivity_test.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 PRIMITIVITY_TEST_H_
34 #define PRIMITIVITY_TEST_H_
35 
36 #include <permlib/prime_helper.h>
37 
38 #include <boost/foreach.hpp>
39 #include <boost/utility.hpp>
40 #include <vector>
41 #include <list>
42 #include <set>
43 
44 namespace permlib {
45 
47 
54 template<typename PERM>
56 public:
64  template<typename InputIterator>
65  PrimitivityTest(const unsigned int n, InputIterator genBegin, InputIterator genEnd);
66 
74  bool blockOfImprimitivity(std::vector<dom_int>* minimalBlock) const;
75 
83  bool allBlocks(std::list<std::vector<dom_int> >* blocks, bool findOnlyOneBlock = false) const;
84 
88  bool isPrimitive() const { return blockOfImprimitivity(NULL); }
89 
90 private:
91  const unsigned int m_n;
92  unsigned int m_primeLimit;
93  const std::list<typename PERM::ptr> m_generators;
94 
95  bool fillTrivialBlock(std::list<std::vector<dom_int> >* block) const;
96 
97  static dom_int rep(dom_int kappa, std::vector<dom_int>& p);
98 
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;
100 };
101 
102 
103 
104 template<typename PERM>
105 template<typename InputIterator>
106 PrimitivityTest<PERM>::PrimitivityTest(const unsigned int n, InputIterator genBegin, InputIterator genEnd)
107  : m_n(n), m_primeLimit(m_n), m_generators(genBegin, genEnd)
108 {
109  for (const unsigned int* p = PrimeHelper::firstPrime(); p != PrimeHelper::lastPrime(); ++p) {
110  if (m_n % (*p) == 0) {
111  m_primeLimit = m_n / (*p);
112  break;
113  }
114  }
115 }
116 
117 template<typename PERM>
118 bool PrimitivityTest<PERM>::blockOfImprimitivity(std::vector<dom_int>* minimalBlock) const {
119  if (minimalBlock) {
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));
125  return is_primitive;
126  }
127  return allBlocks(0, true);
128 }
129 
130 
131 template<typename PERM>
132 bool PrimitivityTest<PERM>::allBlocks(std::list<std::vector<dom_int> >* blocks, bool findOnlyOneBlock) const {
133  std::vector<dom_int> alphas(2);
134  std::set<dom_int> workedAlphas;
135  alphas[0] = 0;
136 
137  for (dom_int a = 1; a < m_n; ++a) {
138  if (workedAlphas.count(a))
139  continue;
140  alphas[1] = a;
141 
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);
147 
148  for (unsigned int i = 0; i < m_n; ++i) {
149  c[i] = 1;
150  p[i] = i;
151  }
152 
153  for (unsigned int i = 0; i < k - 1; ++i) {
154  p[alphas[i+1]] = alphas[0];
155  q[i] = alphas[i+1];
156  }
157 
158  c[alphas[0]] = k;
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)) {
164  goto TRY_NEXT_ALPHA;
165  }
166  }
167  }
168 
169  for (unsigned int i = 0; i < m_n; ++i)
170  rep(i, p);
171 
172  if (c[rep(alphas[0], p)] < m_n) {
173  if (blocks) {
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]]) {
178  block.push_back(i);
179  if (i != alphas[0])
180  workedAlphas.insert(i);
181  }
182  }
183  BOOST_ASSERT( block.size() == c[rep(alphas[0], p)] );
184  blocks->push_back(block);
185  }
186  if (findOnlyOneBlock)
187  return false;
188  }
189 
190  // end of alpha loop
191 TRY_NEXT_ALPHA:
192  continue;
193  }
194 
195  if (!blocks->empty())
196  return false;
197  return fillTrivialBlock(blocks);
198 }
199 
200 template<typename PERM>
201 bool PrimitivityTest<PERM>::fillTrivialBlock(std::list<std::vector<dom_int> >* blocks) const {
202  if (blocks) {
203  std::vector<dom_int> minimalBlock(m_n);
204  for (unsigned int i = 0; i < m_n; ++i)
205  minimalBlock[i] = i;
206  blocks->push_back(minimalBlock);
207  }
208  return true;
209 }
210 
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) {
216  lambda = rho;
217  rho = p[lambda];
218  }
219 
220  dom_int mu = kappa;
221  rho = p[mu];
222  while (rho != lambda) {
223  p[mu] = lambda;
224  mu = rho;
225  rho = p[mu];
226  }
227 
228  return lambda;
229 }
230 
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);
235 
236  if (phi != psi) {
237  dom_int mu, nu;
238  if (c[phi] >= c[psi]) {
239  mu = phi;
240  nu = psi;
241  } else {
242  mu = psi;
243  nu = phi;
244  }
245  p[nu] = mu;
246  c[mu] += c[nu];
247  if (c[mu] > m_primeLimit)
248  return true;
249 
250  q[l] = nu;
251  ++l;
252  }
253 
254  return false;
255 }
256 
257 }
258 
259 #endif
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