permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
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
44namespace permlib {
45
47
54template<typename PERM>
56public:
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
90private:
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
104template<typename PERM>
105template<typename InputIterator>
106PrimitivityTest<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
117template<typename PERM>
118bool 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
131template<typename PERM>
132bool 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
191TRY_NEXT_ALPHA:
192 continue;
193 }
194
195 if (!blocks->empty())
196 return false;
197 return fillTrivialBlock(blocks);
198}
199
200template<typename PERM>
201bool 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
211template<typename PERM>
212dom_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
231template<typename PERM>
232bool 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
static const unsigned int * firstPrime()
iterator pointing to the first prime in list
Definition prime_helper.h:73
static const unsigned int * lastPrime()
iterator pointing after the last prime in list
Definition prime_helper.h:75
Tests a transitive group is availble for primitivity.
Definition primitivity_test.h:55
bool blockOfImprimitivity(std::vector< dom_int > *minimalBlock) const
Definition primitivity_test.h:118
bool isPrimitive() const
Definition primitivity_test.h:88
PrimitivityTest(const unsigned int n, InputIterator genBegin, InputIterator genEnd)
Definition primitivity_test.h:106
bool allBlocks(std::list< std::vector< dom_int > > *blocks, bool findOnlyOneBlock=false) const
Definition primitivity_test.h:132