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_