permlib  0.2.9
Library for permutation computations
permutationword.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 PERMUTATIONWORD_H_
34 #define PERMUTATIONWORD_H_
35 
36 #include <permlib/permutation.h>
37 #include <vector>
38 
39 #include <boost/shared_ptr.hpp>
40 #include <boost/foreach.hpp>
41 
42 namespace permlib {
43 
44 typedef boost::shared_ptr<Permutation> PermutationPtr;
45 
47 
51 public:
54 
56  typedef boost::shared_ptr<PermutationWord> ptr;
57 
59  explicit PermutationWord(unsigned int n);
61  PermutationWord(unsigned int n, const std::string &cycles);
63  explicit PermutationWord(const perm &p);
66 
70 
75 
80  PermutationWord operator~() const;
84  bool operator==(const PermutationWord &p2) const;
85 
87  inline unsigned long operator/(unsigned long val) const { return at(val); }
89  unsigned long at(unsigned long val) const;
91  unsigned long operator%(unsigned long val) const;
92 
94  friend std::ostream &operator<< (std::ostream &out, const PermutationWord &p);
95 
97 
101  bool isIdentity(bool flush = false) const;
102 
104  //TODO: it must be the other way round: isIdentity should call flush
105  inline void flush() { isIdentity(true); }
107  inline unsigned int size() const { return m_n; }
108 
110  static unsigned long elementsNumber() { return ms_elements.size(); }
111 
113  static void clearStorage();
114 private:
115  static std::vector<PermutationPtr> ms_elements;
116  static std::vector<PermutationPtr> ms_elementsInverse;
117  static void addElement(const perm &p);
118  static void addElement(const perm &p, const perm &pInv);
119  static void addElement(PermutationPtr p);
120 
121  mutable std::vector<int> m_word;
122  unsigned int m_n;
123 };
124 
125 std::vector<PermutationPtr> PermutationWord::ms_elements(1);
126 std::vector<PermutationPtr> PermutationWord::ms_elementsInverse(1);
127 
128 inline PermutationWord::PermutationWord(unsigned int n)
129  : m_n(n)
130 { }
131 
132 inline PermutationWord::PermutationWord(unsigned int n, const std::string &cycles)
133  : m_n(n)
134 {
135  Permutation *pp = new Permutation(n, cycles);
136  ms_elements.push_back(PermutationPtr(pp));
137  ms_elementsInverse.push_back(PermutationPtr(new Permutation(~*pp)));
138  m_word.reserve(2);
139  m_word.push_back(ms_elements.size()-1);
140 }
141 
143  : m_word(p.m_word), m_n(p.m_n)
144 { }
145 
147  : m_n(p.size())
148 {
149  addElement(p);
150  m_word.reserve(2);
151  m_word.push_back(ms_elements.size()-1);
152 }
153 
154 inline void PermutationWord::addElement(const perm &p) {
155  PermutationPtr gen(new Permutation(p));
156  ms_elements.push_back(gen);
157  PermutationPtr genInv(new Permutation(~*gen));
158  ms_elementsInverse.push_back(genInv);
159 }
160 inline void PermutationWord::addElement(PermutationPtr p) {
161  ms_elements.push_back(p);
162  PermutationPtr genInv(new Permutation(~*p));
163  ms_elementsInverse.push_back(genInv);
164 }
165 
166 inline void PermutationWord::addElement(const perm &p, const perm &pInv) {
167  PermutationPtr gen(new Permutation(p));
168  ms_elements.push_back(gen);
169  PermutationPtr genInv(new Permutation(pInv));
170  ms_elementsInverse.push_back(genInv);
171 }
172 
173 
175  PermutationWord res(*this);
176  res *= p;
177  return res;
178 }
179 
181  if (m_word.empty()) {
182  m_word.insert(m_word.end(), p.m_word.begin(), p.m_word.end());
183  return *this;
184  } else if (p.m_word.empty())
185  return *this;
186 
187  m_word.insert(m_word.end(), p.m_word.begin(), p.m_word.end());
188  return *this;
189 }
190 
192  if (m_word.empty()) {
193  m_word.insert(m_word.end(), p.m_word.begin(), p.m_word.end());
194  return *this;
195  } else if (p.m_word.empty())
196  return *this;
197 
198  m_word.insert(m_word.begin(), p.m_word.begin(), p.m_word.end());
199  return *this;
200 }
201 
202 
204  std::vector<int> oldWord(m_word);
205  for (unsigned int i=0; i<oldWord.size(); ++i) {
206  m_word[i] = -oldWord[oldWord.size() - 1 - i];
207  }
208  return *this;
209 }
210 
212  PermutationWord inv(*this);
213  for (unsigned int i=0; i<m_word.size(); ++i) {
214  inv.m_word[i] = -m_word[m_word.size() - 1 - i];
215  }
216  return inv;
217 }
218 
219 inline unsigned long PermutationWord::at(unsigned long val) const {
220  unsigned long ret = val;
221  BOOST_FOREACH(int e, m_word) {
222  if (e > 0)
223  ret = *(ms_elements[e]) / ret;
224  else
225  ret = *(ms_elementsInverse[-e]) / ret;
226  }
227  return ret;
228 }
229 
230 inline unsigned long PermutationWord::operator%(unsigned long val) const {
231  unsigned long ret = val;
232  for (std::vector<int>::reverse_iterator lit = m_word.rbegin(); lit != m_word.rend(); ++lit) {
233  int e = *lit;
234  if (e < 0)
235  ret = *(ms_elements[-e]) / ret;
236  else
237  ret = *(ms_elementsInverse[e]) / ret;
238  }
239  return ret;
240 }
241 
242 inline bool PermutationWord::isIdentity(bool flush_) const {
243  if (m_word.empty()) {
244  return true;
245  }
246  if (m_word.size() == 1) {
247  if (flush_)
248  return true;
249  int e = m_word.front();
250  if (e>0)
251  return ms_elements[e]->isIdentity();
252  else
253  return ms_elementsInverse[-e]->isIdentity();
254  }
255 
256  perm mult(m_n);
257  perm multInv(m_n);
258 
259  PermutationPtr resMult(new Permutation(m_n));
260  BOOST_FOREACH(int e, m_word) {
261  *resMult *= (e > 0)
262  ? *ms_elements[e].get()
263  : *ms_elementsInverse[-e].get();
264  }
265 
266  const bool permIsIdentity = resMult->isIdentity();
267 
268  if (!permIsIdentity) {
269  addElement(resMult);
270  m_word.clear();
271  m_word.reserve(2);
272  m_word.push_back(ms_elements.size()-1);
273  }
274 
275 
276  return permIsIdentity;
277 }
278 
279 inline std::ostream &operator<< (std::ostream &out, const PermutationWord &p) {
280  out << "W[";
281  BOOST_FOREACH(int g, p.m_word) {
282  out << g << ",";
283  }
284  out << "]";
285  return out;
286 }
287 
288 inline bool PermutationWord::operator==(const PermutationWord &p2) const {
289  if (m_n != p2.m_n)
290  return false;
291 
292  //TODO: is this correct or do we need the old code (below) or keep references to all perm instances?
293  //note: this is not correct: compare result of \inv{g} * g and g * \inv{g}, but this can be fixed by .... -x x ...... stripping when multiplying
294  // in other cases it might have a good chance to work as intended
295  //
296  // NOTE: old code deleted from below during clean-up
297  return m_word == p2.m_word;
298 }
299 
301  ms_elements.clear();
302  ms_elements.resize(1);
303  ms_elementsInverse.clear();
304  ms_elementsInverse.resize(1);
305 }
306 
307 }
308 
309 #endif // -- PERMUTATIONWORD_H_
unsigned long operator%(unsigned long val) const
lets inverse permutation act on val, i.e. compute j such that (this->at(j) == val) ...
Definition: permutationword.h:230
bool operator==(const PermutationWord &p2) const
equals operator
Definition: permutationword.h:288
static void clearStorage()
deletes all elementary permutations from the storage. use ONLY if there is currently no PermutationWo...
Definition: permutationword.h:300
friend std::ostream & operator<<(std::ostream &out, const PermutationWord &p)
output
Definition: permutationword.h:279
PermutationWord & operator^=(const PermutationWord &p)
permutation inplace multiplication from the left
Definition: permutationword.h:191
PermutationWord(unsigned int n)
constructs identity permutation acting on n elements
Definition: permutationword.h:128
PermutationWord & operator*=(const PermutationWord &p)
permutation inplace multiplication from the right
Definition: permutationword.h:180
void flush()
force that permutation word is multiplied out
Definition: permutationword.h:105
unsigned long at(unsigned long val) const
lets permutation act on val
Definition: permutationword.h:219
unsigned long operator/(unsigned long val) const
lets permutation act on val
Definition: permutationword.h:87
bool isIdentity(bool flush=false) const
returns true if this permutation is identity
Definition: permutationword.h:242
PermutationWord & invertInplace()
permutation inplace inversion
Definition: permutationword.h:203
PermutationWord operator~() const
permutation inversion
Definition: permutationword.h:211
PermutationWord operator*(const PermutationWord &p) const
permutation multiplication from the right
Definition: permutationword.h:174
unsigned int size() const
number of points this permutation acts on
Definition: permutationword.h:107
permutation class storing permutations as words of elementary Permutation &#39;s
Definition: permutationword.h:50
std::vector< dom_int > perm
typedef for permutation image
Definition: permutation.h:61
Permutation class storing all values explicitly.
Definition: permutation.h:58
Permutation::perm perm
typedef for permutation image
Definition: permutationword.h:53
static unsigned long elementsNumber()
number of generators in the word generator pool
Definition: permutationword.h:110
boost::shared_ptr< PermutationWord > ptr
boost shared_ptr of this class
Definition: permutationword.h:56
Definition: abstract_bsgs.h:49