33 #ifndef PERMUTATION_H_ 34 #define PERMUTATION_H_ 36 #include <permlib/common.h> 41 #include <boost/tokenizer.hpp> 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> 55 namespace exports {
struct BSGSSchreierExport; }
61 typedef std::vector<dom_int>
perm;
64 typedef boost::shared_ptr<Permutation>
ptr;
77 template<
class InputIterator>
102 inline dom_int
at(dom_int val)
const {
return m_perm[val]; }
125 std::list<std::pair<dom_int, unsigned int> >
cycles(
bool includeTrivialCycles =
false)
const;
131 boost::uint64_t
order()
const;
141 template<
typename ForwardIterator>
142 Permutation*
project(
unsigned int n_proj, ForwardIterator begin, ForwardIterator end)
const;
168 : m_perm(n), m_isIdentity(true)
170 for (dom_int i=0; i<n; ++i)
175 typedef boost::tokenizer<boost::char_separator<char> > tokenizer;
176 boost::char_separator<char> sepCycles(
",");
177 tokenizer tokens(cycleString, sepCycles);
179 for (dom_int i=0; i<
m_perm.size(); ++i)
182 #ifdef PERMLIB_DEBUGMODE 183 boost::dynamic_bitset<> seenIndices(
m_perm.size());
186 for (tokenizer::iterator tok_iter = tokens.begin(); tok_iter != tokens.end(); ++tok_iter) {
187 std::stringstream ss(*tok_iter);
189 unsigned int first, last, temp;
192 #ifdef PERMLIB_DEBUGMODE 193 BOOST_ASSERT( !seenIndices[first-1] );
194 seenIndices.set(first-1, 1);
198 #ifdef PERMLIB_DEBUGMODE 199 BOOST_ASSERT( !seenIndices[temp-1] );
200 seenIndices.set(temp-1, 1);
211 : m_perm(n), m_isIdentity(false)
217 : m_perm(n), m_isIdentity(false)
224 : m_perm(p), m_isIdentity(false)
226 #ifdef PERMLIB_DEBUGMODE 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() );
234 BOOST_ASSERT( values.size() ==
m_perm.size() );
242 for (dom_int i=0; i<
m_perm.size(); ++i) {
253 for (dom_int i=0; i<
m_perm.size(); ++i) {
266 for (dom_int i=0; i<
m_perm.size(); ++i) {
274 for (dom_int i=0; i<
m_perm.size(); ++i) {
282 for (dom_int i=0; i<
m_perm.size(); ++i) {
289 for (dom_int i = 0; i <
m_perm.size(); ++i) {
301 for (dom_int i=0; i<
m_perm.size(); ++i)
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;
313 for (dom_int x=0; x<
m_perm.size(); ++x) {
322 if (includeTrivialCycles)
323 cycleList.push_back(CyclePair(x, 1));
329 while (
m_perm[px] != startX) {
335 cycleList.push_back(CyclePair(startX, cycleLength));
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));
351 template<
typename ForwardIterator>
353 std::map<dom_int, dom_int> projectionMap;
355 for (ForwardIterator it = begin; it != end; ++it) {
356 projectionMap[*it] = c++;
360 bool is_identity =
true;
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;
372 if (proj_x != proj_px)
382 BOOST_ASSERT(pos <
m_perm.size());
383 BOOST_ASSERT(val <
m_perm.size());
389 inline std::ostream& operator<<(std::ostream& out,
const Permutation& p) {
390 typedef std::pair<dom_int, unsigned int> CyclePair;
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) {
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