33 #ifndef TRANSVERSAL_H_
34 #define TRANSVERSAL_H_
36 #include <permlib/sorter/base_sorter.h>
37 #include <permlib/transversal/orbit.h>
43 #include <boost/foreach.hpp>
44 #include <boost/shared_ptr.hpp>
52 std::ostream &operator<< (std::ostream &out, const Transversal<PERM> &t) {
54 BOOST_FOREACH (boost::shared_ptr<PERM> p, t.m_transversal) {
77 virtual PERM*
at(
unsigned long val)
const = 0;
83 virtual bool contains(
const unsigned long& val)
const;
86 std::list<unsigned long>::const_iterator
begin()
const {
return this->
m_orbit.begin(); };
88 std::list<unsigned long>::const_iterator
end()
const {
return this->
m_orbit.end(); };
90 std::pair<std::list<unsigned long>::const_iterator,std::list<unsigned long>::const_iterator>
pairIt()
const {
91 return std::make_pair(
begin(),
end());
98 inline unsigned int n()
const {
return m_n; }
105 template <
class InputIterator>
106 void sort(InputIterator Bbegin, InputIterator Bend);
114 unsigned long operator()(
const PERM &p,
unsigned long v)
const {
124 virtual void orbit(
unsigned long alpha,
const std::list<typename PERM::ptr> &generators);
131 virtual void orbitUpdate(
unsigned long alpha,
const std::list<typename PERM::ptr> &generators,
const typename PERM::ptr &g);
138 virtual void permute(
const PERM& g,
const PERM& gInv);
143 virtual void updateGenerators(
const std::map<PERM*,typename PERM::ptr>& generatorChange) {}
145 virtual const unsigned long&
element()
const;
148 friend std::ostream &operator<< <> (std::ostream &out,
const Transversal<PERM> &p);
163 virtual void registerMove(
unsigned long from,
unsigned long to,
const typename PERM::ptr &p);
165 virtual bool foundOrbitElement(
const unsigned long& alpha,
const unsigned long& alpha_p,
const typename PERM::ptr& p);
172 template <
class PERM>
174 : m_n(n_), m_transversal(n_), m_sorted(false)
177 template <
class PERM>
182 template <
class PERM>
187 template <
class PERM>
189 BOOST_ASSERT( alpha_p < m_transversal.size() );
190 if (!m_transversal[alpha_p]) {
192 typename PERM::ptr identity(
new PERM(m_n));
193 registerMove(alpha, alpha_p, identity);
195 registerMove(alpha, alpha_p, p);
202 template <
class PERM>
204 return m_transversal[val] != 0;
207 template <
class PERM>
213 template <
class PERM>
214 template <
class InputIterator>
216 this->m_orbit.sort(
BaseSorter(m_n, Bbegin, Bend));
220 template <
class PERM>
222 std::vector<boost::shared_ptr<PERM> > temp(m_n);
223 for (
unsigned long i=0; i<m_n; ++i) {
224 const unsigned long j = g / i;
225 temp[j] = m_transversal[i];
227 std::copy(temp.begin(), temp.end(), m_transversal.begin());
228 BOOST_FOREACH(
unsigned long& alpha, this->m_orbit) {
234 template <
class PERM>
236 return m_orbit.front();
241 #endif // -- TRANSVERSAL_H_