permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
permutation.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 PERMUTATION_H_
34#define PERMUTATION_H_
35
36#include <permlib/common.h>
37
38// for I/O
39#include <string>
40#include <iostream>
41#include <boost/tokenizer.hpp>
42#include <sstream>
43#include <set>
44#include <list>
45#include <map>
46
47#include <boost/shared_ptr.hpp>
48#include <boost/dynamic_bitset.hpp>
49#include <boost/foreach.hpp>
50#include <boost/cstdint.hpp>
51#include <boost/integer/common_factor_rt.hpp>
52
53namespace permlib {
54
55namespace exports { struct BSGSSchreierExport; }
56
59public:
61 typedef std::vector<dom_int> perm;
62
64 typedef boost::shared_ptr<Permutation> ptr;
65
67 explicit Permutation(dom_int n);
69 Permutation(dom_int n, const std::string &cycles);
71 Permutation(dom_int n, const char* cycles);
73 explicit Permutation(const perm &p);
77 template<class InputIterator>
78 Permutation(InputIterator begin, InputIterator end) : m_perm(begin, end), m_isIdentity(false) {}
79
81 Permutation operator*(const Permutation &p) const;
83
88
93 Permutation operator~() const;
97 bool operator==(const Permutation &p2) const { return m_perm == p2.m_perm; };
98
100 inline dom_int operator/(dom_int val) const { return at(val); }
102 inline dom_int at(dom_int val) const { return m_perm[val]; }
103
105 dom_int operator%(dom_int val) const;
106
108 friend std::ostream &operator<< (std::ostream &out, const Permutation &p);
109
111
114 bool isIdentity() const;
116 inline void flush() {};
118 inline dom_int size() const { return m_perm.size(); }
119
121
125 std::list<std::pair<dom_int, unsigned int> > cycles(bool includeTrivialCycles = false) const;
126
128
131 boost::uint64_t order() const;
132
134
141 template<typename ForwardIterator>
142 Permutation* project(unsigned int n_proj, ForwardIterator begin, ForwardIterator end) const;
143
145 void setTransposition(dom_int pos, dom_int val);
146protected:
149
152
154 Permutation(dom_int n, bool) : m_perm(n), m_isIdentity(false) {}
155
157 void initFromCycleString(const std::string& cycles);
158
160};
161
162
163//
164// ---- IMPLEMENTATION
165//
166
167inline Permutation::Permutation(dom_int n)
168 : m_perm(n), m_isIdentity(true)
169{
170 for (dom_int i=0; i<n; ++i)
171 m_perm[i] = i;
172}
173
174inline void Permutation::initFromCycleString(const std::string& cycleString) {
175 typedef boost::tokenizer<boost::char_separator<char> > tokenizer;
176 boost::char_separator<char> sepCycles(",");
177 tokenizer tokens(cycleString, sepCycles);
178
179 for (dom_int i=0; i<m_perm.size(); ++i)
180 m_perm[i] = i;
181
182#ifdef PERMLIB_DEBUGMODE
183 boost::dynamic_bitset<> seenIndices(m_perm.size());
184#endif
185
186 for (tokenizer::iterator tok_iter = tokens.begin(); tok_iter != tokens.end(); ++tok_iter) {
187 std::stringstream ss(*tok_iter);
188
189 unsigned int first, last, temp;
190 ss >> first;
191 last = first;
192#ifdef PERMLIB_DEBUGMODE
193 BOOST_ASSERT( !seenIndices[first-1] );
194 seenIndices.set(first-1, 1);
195#endif
196
197 while (ss >> temp) {
198#ifdef PERMLIB_DEBUGMODE
199 BOOST_ASSERT( !seenIndices[temp-1] );
200 seenIndices.set(temp-1, 1);
201#endif
202 m_perm[last-1] = temp-1;
203 last = temp;
204 }
205 m_perm[last-1] = first-1;
206 }
207}
208
209
210inline Permutation::Permutation(dom_int n, const std::string & cycleString)
211 : m_perm(n), m_isIdentity(false)
212{
213 initFromCycleString(cycleString);
214}
215
216inline Permutation::Permutation(dom_int n, const char* cycleString)
217 : m_perm(n), m_isIdentity(false)
218{
219 initFromCycleString(std::string(cycleString));
220}
221
222
224 : m_perm(p), m_isIdentity(false)
225{
226#ifdef PERMLIB_DEBUGMODE
227 // check that m_perm really is a permutation
228 std::set<dom_int> values;
229 for (dom_int i=0; i<m_perm.size(); ++i) {
230 const dom_int& v = m_perm[i];
231 BOOST_ASSERT( v < m_perm.size() );
232 values.insert(v);
233 }
234 BOOST_ASSERT( values.size() == m_perm.size() );
235#endif
236}
237
239 BOOST_ASSERT(p.m_perm.size() == m_perm.size());
240
241 Permutation res(m_perm.size(), true);
242 for (dom_int i=0; i<m_perm.size(); ++i) {
243 res.m_perm[i] = p.m_perm[m_perm[i]];
244 }
245 return res;
246}
247
249 BOOST_ASSERT(p.m_perm.size() == m_perm.size());
250 m_isIdentity = false;
251 perm tmp(m_perm);
252
253 for (dom_int i=0; i<m_perm.size(); ++i) {
254 tmp[i] = p.m_perm[m_perm[i]];
255 }
256 m_perm = tmp;
257
258 return *this;
259}
260
262 BOOST_ASSERT(p.m_perm.size() == m_perm.size());
263 m_isIdentity = false;
264 perm tmp(m_perm);
265
266 for (dom_int i=0; i<m_perm.size(); ++i) {
267 m_perm[i] = tmp[p.m_perm[i]];
268 }
269 return *this;
270}
271
273 Permutation res(m_perm.size(), true);
274 for (dom_int i=0; i<m_perm.size(); ++i) {
275 res.m_perm[m_perm[i]] = i;
276 }
277 return res;
278}
279
281 perm tmp(m_perm);
282 for (dom_int i=0; i<m_perm.size(); ++i) {
283 m_perm[tmp[i]] = i;
284 }
285 return *this;
286}
287
288inline dom_int Permutation::operator%(dom_int val) const {
289 for (dom_int i = 0; i < m_perm.size(); ++i) {
290 if (m_perm[i] == val)
291 return i;
292 }
293 // must not happen, we have a permutation!
294 BOOST_ASSERT(false);
295 return -1;
296}
297
298inline bool Permutation::isIdentity() const {
299 if (m_isIdentity)
300 return true;
301 for (dom_int i=0; i<m_perm.size(); ++i)
302 if (at(i) != i)
303 return false;
304 return true;
305}
306
307inline std::list<std::pair<dom_int, unsigned int> > Permutation::cycles(bool includeTrivialCycles) const {
308 boost::dynamic_bitset<> worked(m_perm.size());
309 typedef std::pair<dom_int, unsigned int> CyclePair;
310 std::list<CyclePair> cycleList;
311 unsigned int cycleLength = 0;
312
313 for (dom_int x=0; x<m_perm.size(); ++x) {
314 if (worked[x])
315 continue;
316
317 dom_int px, startX;
318 worked.set(x, 1);
319 startX = x;
320 px = m_perm[x];
321 if (x == px) {
322 if (includeTrivialCycles)
323 cycleList.push_back(CyclePair(x, 1));
324 continue;
325 }
326
327 cycleLength = 2;
328
329 while (m_perm[px] != startX) {
330 worked.set(px, 1);
331 px = m_perm[px];
332 ++cycleLength;
333 }
334 worked.set(px, 1);
335 cycleList.push_back(CyclePair(startX, cycleLength));
336 }
337
338 return cycleList;
339}
340
341inline boost::uint64_t Permutation::order() const {
342 typedef std::pair<dom_int, unsigned int> CyclePair;
343 std::list<CyclePair> cycleList = this->cycles();
344 boost::uint64_t ord = 1;
345 BOOST_FOREACH(const CyclePair& cyc, cycleList) {
346 ord = boost::integer::lcm(ord, static_cast<boost::uint64_t>(cyc.second));
347 }
348 return ord;
349}
350
351template<typename ForwardIterator>
352Permutation* Permutation::project(unsigned int n_proj, ForwardIterator begin, ForwardIterator end) const {
353 std::map<dom_int, dom_int> projectionMap;
354 dom_int c = 0;
355 for (ForwardIterator it = begin; it != end; ++it) {
356 projectionMap[*it] = c++;
357 }
358
359 Permutation* proj = new Permutation(n_proj);
360 bool is_identity = true;
361
362 while (begin != end) {
363 dom_int x = *begin++;
364 BOOST_ASSERT( projectionMap.find(x) != projectionMap.end() );
365 BOOST_ASSERT( projectionMap.find(m_perm[x]) != projectionMap.end() );
366 const dom_int proj_x = projectionMap[x];
367 const dom_int proj_px = projectionMap[ m_perm[x] ];
368 BOOST_ASSERT( proj_x < n_proj );
369 BOOST_ASSERT( proj_px < n_proj );
370 proj->m_perm[ proj_x ] = proj_px;
371
372 if (proj_x != proj_px)
373 is_identity = false;
374 }
375
376 proj->m_isIdentity = is_identity;
377
378 return proj;
379}
380
381inline void Permutation::setTransposition(dom_int pos, dom_int val) {
382 BOOST_ASSERT(pos < m_perm.size());
383 BOOST_ASSERT(val < m_perm.size());
384
385 m_perm[pos] = val;
386 m_perm[val] = pos;
387}
388
389inline std::ostream& operator<<(std::ostream& out, const Permutation& p) {
390 typedef std::pair<dom_int, unsigned int> CyclePair;
391 bool output = false;
392
393 std::list<CyclePair> cycleList = p.cycles();
394 BOOST_FOREACH(const CyclePair& c, cycleList) {
395 dom_int px = p / c.first;
396 out << "(" << (c.first + 1) << ",";
397 while (px != c.first) {
398 out << (px+1);
399 px = p / px;
400 if (px == c.first)
401 out << ")";
402 else
403 out << ",";
404 }
405 output = true;
406 }
407
408 if (!output)
409 out << "()";
410
411 return out;
412}
413
414}
415
416#endif // -- PERMUTATION_H_
Permutation class storing all values explicitly.
Definition permutation.h:58
dom_int at(dom_int val) const
lets permutation act on val
Definition permutation.h:102
Permutation(dom_int n)
constructs identity permutation acting on n elements
Definition permutation.h:167
void setTransposition(dom_int pos, dom_int val)
updates this permutation such that pos is mapped onto val and val onto pos
Definition permutation.h:381
Permutation & operator^=(const Permutation &p)
permutation inplace multiplication from the left
Definition permutation.h:261
Permutation operator*(const Permutation &p) const
permutation multiplication from the right
Definition permutation.h:238
Permutation(const Permutation &p)
copy constructor
Definition permutation.h:75
Permutation(InputIterator begin, InputIterator end)
construct from dom_int-iterator
Definition permutation.h:78
dom_int size() const
number of points this permutation acts on
Definition permutation.h:118
bool isIdentity() const
returns true if this permutation is identity
Definition permutation.h:298
Permutation & invertInplace()
permutation inplace inversion
Definition permutation.h:280
bool m_isIdentity
if set to true, permutation is identity; if set to false then it is not known whether this is identit...
Definition permutation.h:151
dom_int operator/(dom_int val) const
lets permutation act on val
Definition permutation.h:100
Permutation * project(unsigned int n_proj, ForwardIterator begin, ForwardIterator end) const
restricts this permutation p to a subset S of the domain
Definition permutation.h:352
std::vector< dom_int > perm
typedef for permutation image
Definition permutation.h:61
Permutation(dom_int n, bool)
INTERNAL ONLY: constructs an "empty" permutation, i.e. without element mapping.
Definition permutation.h:154
boost::uint64_t order() const
computes the order of this permutation
Definition permutation.h:341
void initFromCycleString(const std::string &cycles)
initializes permutation data from a string in cycle form
Definition permutation.h:174
Permutation operator~() const
permutation inversion
Definition permutation.h:272
friend std::ostream & operator<<(std::ostream &out, const Permutation &p)
output in cycle form
Definition permutation.h:389
boost::shared_ptr< Permutation > ptr
boost shared_ptr of this class
Definition permutation.h:64
void flush()
dummy stub for interface compatability with PermutationWord
Definition permutation.h:116
perm m_perm
defintion of permutation behavior
Definition permutation.h:148
Permutation & operator*=(const Permutation &p)
permutation inplace multiplication from the right
Definition permutation.h:248
bool operator==(const Permutation &p2) const
equals operator
Definition permutation.h:97
dom_int operator%(dom_int val) const
lets inverse permutation act on val, i.e. compute j such that (this->at(j) == val)
Definition permutation.h:288
std::list< std::pair< dom_int, unsigned int > > cycles(bool includeTrivialCycles=false) const
computes all cycles of this permutation
Definition permutation.h:307
export of a BSGS based on SchreierTreeTransversal
Definition bsgs_schreier_export.h:99