permlib  0.2.8
Library for permutation computations
 All Classes Functions Variables Typedefs Enumerations Friends
transversal.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 TRANSVERSAL_H_
34 #define TRANSVERSAL_H_
35 
36 #include <permlib/sorter/base_sorter.h>
37 #include <permlib/transversal/orbit.h>
38 
39 #include <map>
40 #include <list>
41 #include <vector>
42 
43 #include <boost/foreach.hpp>
44 #include <boost/shared_ptr.hpp>
45 
46 namespace permlib {
47 
48 template <class PERM>
49 class Transversal;
50 
51 template <class PERM>
52 std::ostream &operator<< (std::ostream &out, const Transversal<PERM> &t) {
53  out << "{";
54  BOOST_FOREACH (boost::shared_ptr<PERM> p, t.m_transversal) {
55  if (p)
56  out << *p << ", ";
57  else
58  out << "O, ";
59  }
60  out << "}";
61  return out;
62 }
63 
65 template <class PERM>
66 class Transversal : public Orbit<PERM,unsigned long> {
67 public:
69 
72  Transversal(unsigned int n);
74  virtual ~Transversal() {}
75 
77  virtual PERM* at(unsigned long val) const = 0;
78 
80  virtual bool trivialByDefinition(const PERM& x, unsigned long to) const = 0;
81 
83  virtual bool contains(const unsigned long& val) const;
84 
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());
92  }
93 
95  size_t size() const { return this->m_orbit.size(); }
96 
98  inline unsigned int n() const { return m_n; }
99 
101 
105  template <class InputIterator>
106  void sort(InputIterator Bbegin, InputIterator Bend);
107 
109  inline bool sorted() const { return m_sorted; }
110 
112  struct TrivialAction {
114  unsigned long operator()(const PERM &p, unsigned long v) const {
115  return p / v;
116  }
117  };
118 
120 
124  virtual void orbit(unsigned long alpha, const std::list<typename PERM::ptr> &generators);
126 
131  virtual void orbitUpdate(unsigned long alpha, const std::list<typename PERM::ptr> &generators, const typename PERM::ptr &g);
132 
134 
138  virtual void permute(const PERM& g, const PERM& gInv);
140 
143  virtual void updateGenerators(const std::map<PERM*,typename PERM::ptr>& generatorChange) {}
144 
145  virtual const unsigned long& element() const;
146 
148  friend std::ostream &operator<< <> (std::ostream &out, const Transversal<PERM> &p);
149 protected:
151  unsigned int m_n;
152 
154  std::vector<boost::shared_ptr<PERM> > m_transversal;
155 
157  std::list<unsigned long> m_orbit;
158 
160  bool m_sorted;
161 
163  virtual void registerMove(unsigned long from, unsigned long to, const typename PERM::ptr &p);
164 
165  virtual bool foundOrbitElement(const unsigned long& alpha, const unsigned long& alpha_p, const typename PERM::ptr& p);
166 };
167 
168 //
169 // ---- IMPLEMENTATION
170 //
171 
172 template <class PERM>
174  : m_n(n_), m_transversal(n_), m_sorted(false)
175 { }
176 
177 template <class PERM>
178 void Transversal<PERM>::orbit(unsigned long beta, const std::list<typename PERM::ptr> &generators) {
179  Orbit<PERM,unsigned long>::orbit(beta, generators, TrivialAction(), m_orbit);
180 }
181 
182 template <class PERM>
183 void Transversal<PERM>::orbitUpdate(unsigned long beta, const std::list<typename PERM::ptr> &generators, const typename PERM::ptr &g) {
184  Orbit<PERM,unsigned long>::orbitUpdate(beta, generators, g, TrivialAction(), m_orbit);
185 }
186 
187 template <class PERM>
188 bool Transversal<PERM>::foundOrbitElement(const unsigned long& alpha, const unsigned long& alpha_p, const typename PERM::ptr& p) {
189  BOOST_ASSERT( alpha_p < m_transversal.size() );
190  if (!m_transversal[alpha_p]) {
191  if (!p) {
192  typename PERM::ptr identity(new PERM(m_n));
193  registerMove(alpha, alpha_p, identity);
194  } else {
195  registerMove(alpha, alpha_p, p);
196  }
197  return true;
198  }
199  return false;
200 }
201 
202 template <class PERM>
203 bool Transversal<PERM>::contains(const unsigned long& val) const {
204  return m_transversal[val] != 0;
205 }
206 
207 template <class PERM>
208 void Transversal<PERM>::registerMove(unsigned long from, unsigned long to, const typename PERM::ptr &p) {
209  m_sorted = false;
210 }
211 
212 
213 template <class PERM>
214 template <class InputIterator>
215 void Transversal<PERM>::sort(InputIterator Bbegin, InputIterator Bend) {
216  this->m_orbit.sort(BaseSorter(m_n, Bbegin, Bend));
217  m_sorted = true;
218 }
219 
220 template <class PERM>
221 void Transversal<PERM>::permute(const PERM& g, const PERM& gInv) {
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];
226  }
227  std::copy(temp.begin(), temp.end(), m_transversal.begin());
228  BOOST_FOREACH(unsigned long& alpha, this->m_orbit) {
229  alpha = g / alpha;
230  }
231  m_sorted = false;
232 }
233 
234 template <class PERM>
235 inline const unsigned long& Transversal<PERM>::element() const {
236  return m_orbit.front();
237 }
238 
239 }
240 
241 #endif // -- TRANSVERSAL_H_