permlib  0.2.9
Library for permutation computations
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/math/common_factor_rt.hpp>
52 
53 namespace permlib {
54 
55 namespace exports { struct BSGSSchreierExport; }
56 
58 class Permutation {
59 public:
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);
146 protected:
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 
167 inline 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 
174 inline 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 
210 inline Permutation::Permutation(dom_int n, const std::string & cycleString)
211  : m_perm(n), m_isIdentity(false)
212 {
213  initFromCycleString(cycleString);
214 }
215 
216 inline 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 
288 inline 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 
298 inline 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 
307 inline 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 
341 inline 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::math::lcm(ord, static_cast<boost::uint64_t>(cyc.second));
347  }
348  return ord;
349 }
350 
351 template<typename ForwardIterator>
352 Permutation* 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 
381 inline 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 
389 inline 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_
bool isIdentity() const
returns true if this permutation is identity
Definition: permutation.h:298
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
std::list< std::pair< dom_int, unsigned int > > cycles(bool includeTrivialCycles=false) const
computes all cycles of this permutation
Definition: permutation.h:307
Permutation(InputIterator begin, InputIterator end)
construct from dom_int-iterator
Definition: permutation.h:78
bool operator==(const Permutation &p2) const
equals operator
Definition: permutation.h:97
void flush()
dummy stub for interface compatability with PermutationWord
Definition: permutation.h:116
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 * 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
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
boost::uint64_t order() const
computes the order of this permutation
Definition: permutation.h:341
Permutation & invertInplace()
permutation inplace inversion
Definition: permutation.h:280
dom_int size() const
number of points this permutation acts on
Definition: permutation.h:118
void initFromCycleString(const std::string &cycles)
initializes permutation data from a string in cycle form
Definition: permutation.h:174
Permutation(dom_int n)
constructs identity permutation acting on n elements
Definition: permutation.h:167
export of a BSGS based on SchreierTreeTransversal
Definition: bsgs_schreier_export.h:99
Permutation & operator^=(const Permutation &p)
permutation inplace multiplication from the left
Definition: permutation.h:261
Permutation(const Permutation &p)
copy constructor
Definition: permutation.h:75
Permutation & operator*=(const Permutation &p)
permutation inplace multiplication from the right
Definition: permutation.h:248
friend std::ostream & operator<<(std::ostream &out, const Permutation &p)
output in cycle form
Definition: permutation.h:389
Permutation operator~() const
permutation inversion
Definition: permutation.h:272
dom_int at(dom_int val) const
lets permutation act on val
Definition: permutation.h:102
boost::shared_ptr< Permutation > ptr
boost shared_ptr of this class
Definition: permutation.h:64
Permutation(dom_int n, bool)
INTERNAL ONLY: constructs an "empty" permutation, i.e. without element mapping.
Definition: permutation.h:154
std::vector< dom_int > perm
typedef for permutation image
Definition: permutation.h:61
Permutation operator*(const Permutation &p) const
permutation multiplication from the right
Definition: permutation.h:238
dom_int operator/(dom_int val) const
lets permutation act on val
Definition: permutation.h:100
perm m_perm
defintion of permutation behavior
Definition: permutation.h:148
Permutation class storing all values explicitly.
Definition: permutation.h:58
Definition: abstract_bsgs.h:49