permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
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
42namespace permlib {
43
44typedef boost::shared_ptr<Permutation> PermutationPtr;
45
47
51public:
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
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();
114private:
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
125std::vector<PermutationPtr> PermutationWord::ms_elements(1);
126std::vector<PermutationPtr> PermutationWord::ms_elementsInverse(1);
127
128inline PermutationWord::PermutationWord(unsigned int n)
129 : m_n(n)
130{ }
131
132inline 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
154inline 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}
160inline 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
166inline 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
219inline 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
230inline 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
242inline 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
279inline 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
288inline 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_
permutation class storing permutations as words of elementary Permutation 's
Definition permutationword.h:50
unsigned long operator/(unsigned long val) const
lets permutation act on val
Definition permutationword.h:87
static unsigned long elementsNumber()
number of generators in the word generator pool
Definition permutationword.h:110
PermutationWord & operator^=(const PermutationWord &p)
permutation inplace multiplication from the left
Definition permutationword.h:191
PermutationWord & invertInplace()
permutation inplace inversion
Definition permutationword.h:203
friend std::ostream & operator<<(std::ostream &out, const PermutationWord &p)
output
Definition permutationword.h:279
boost::shared_ptr< PermutationWord > ptr
boost shared_ptr of this class
Definition permutationword.h:56
PermutationWord operator~() const
permutation inversion
Definition permutationword.h:211
PermutationWord operator*(const PermutationWord &p) const
permutation multiplication from the right
Definition permutationword.h:174
PermutationWord & operator*=(const PermutationWord &p)
permutation inplace multiplication from the right
Definition permutationword.h:180
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
PermutationWord(unsigned int n)
constructs identity permutation acting on n elements
Definition permutationword.h:128
unsigned int size() const
number of points this permutation acts on
Definition permutationword.h:107
void flush()
force that permutation word is multiplied out
Definition permutationword.h:105
bool operator==(const PermutationWord &p2) const
equals operator
Definition permutationword.h:288
unsigned long at(unsigned long val) const
lets permutation act on val
Definition permutationword.h:219
Permutation::perm perm
typedef for permutation image
Definition permutationword.h:53
bool isIdentity(bool flush=false) const
returns true if this permutation is identity
Definition permutationword.h:242
static void clearStorage()
deletes all elementary permutations from the storage. use ONLY if there is currently no PermutationWo...
Definition permutationword.h:300
Permutation class storing all values explicitly.
Definition permutation.h:58
std::vector< dom_int > perm
typedef for permutation image
Definition permutation.h:61