permlib  0.2.9
Library for permutation computations
abstract_symmetric_product.h
1 // ---------------------------------------------------------------------------
2 //
3 // This file is part of PermLib.
4 //
5 // Copyright (c) 2009-2012 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 #include <boost/shared_ptr.hpp>
33 
34 #include <algorithm>
35 #include <map>
36 #include <permlib/abstract_permutation_group.h>
37 
38 #ifndef ABSTRACT_SYMMETRIC_PRODUCT_H_
39 #define ABSTRACT_SYMMETRIC_PRODUCT_H_
40 
41 namespace permlib {
42 
45 public:
47 
54  template<typename InputIterator>
55  AbstractSymmetricProduct(InputIterator begin, InputIterator end) {
56  for (InputIterator it = begin; it != end; ++it) {
57  m_indices.push_back(std::set<dom_int>((*it).begin(), (*it).end()));
58  }
59  }
60 
61  virtual AbstractPermutationGroup* setStabilizer(const std::vector<dom_int>& s) const;
62  virtual OrbitList* orbits() const;
63  // TODO: must s be sorted?
64  virtual OrbitList* orbits(const std::vector<dom_int>& s) const;
65 
66  virtual bool isLexMinSet(const std::vector<dom_int>& setIndices, const std::vector<dom_int>& rankIndices) const;
67 
68  virtual AbstractGroupType type() const { return AGT_SymmetricProduct; }
69 protected:
70  virtual void transversalSizes(std::vector<unsigned long>& sizes) const;
71 
72 private:
74 
75  typedef std::list<std::set<dom_int> > IndexList;
76  std::list<std::set<dom_int> > m_indices;
77  mutable std::map<dom_int, dom_int> m_indicesReverse;
78 
79  int getOrbitRank(dom_int x) const;
80 };
81 
82 inline void AbstractSymmetricProduct::transversalSizes(std::vector<unsigned long>& sizes) const {
83  sizes.clear();
84  sizes.reserve(m_indices.size());
85  BOOST_FOREACH(const std::set<dom_int>& ind, m_indices) {
86  for (unsigned long x = ind.size(); x > 1; --x)
87  sizes.push_back(x);
88  }
89 }
90 
91 inline AbstractPermutationGroup* AbstractSymmetricProduct::setStabilizer(const std::vector<dom_int>& svec) const {
92  std::set<dom_int> s(svec.begin(), svec.end());
93 
95  BOOST_FOREACH(const std::set<dom_int>& ind, m_indices) {
96  std::set<dom_int> sA, sB;
97  std::set_difference(ind.begin(), ind.end(), s.begin(), s.end(), std::inserter(sA, sA.begin()));
98  if (sA.size() > 1) {
99  stabilizer->m_indices.push_back(sA);
100  }
101  std::set_intersection(ind.begin(), ind.end(), s.begin(), s.end(), std::inserter(sB, sB.begin()));
102  if (sB.size() > 1) {
103  stabilizer->m_indices.push_back(sB);
104  }
105  }
106  return stabilizer;
107 }
108 
110  OrbitList* retList = new OrbitList(m_indices);
111  return retList;
112 }
113 
114 inline AbstractPermutationGroup::OrbitList* AbstractSymmetricProduct::orbits(const std::vector<dom_int>& s) const {
115  OrbitList* retList = new OrbitList();
116  BOOST_FOREACH(const std::set<dom_int>& ind, m_indices) {
117  std::set<dom_int>::const_iterator indIt = std::find_first_of(ind.begin(), ind.end(), s.begin(), s.end());
118  if (indIt != ind.end()) {
119  retList->push_back(ind);
120  }
121  }
122  return retList;
123 }
124 
125 inline bool AbstractSymmetricProduct::isLexMinSet(const std::vector<dom_int>& setIndices, const std::vector<dom_int>& rankIndices) const {
126  std::vector<unsigned int> expectedPosition(m_indices.size());
127 
128  BOOST_FOREACH(dom_int x, setIndices) {
129  // if x is not at expectedPosition of its orbit
130  // return false
131  const int rank = getOrbitRank(x);
132  if (rank < 0)
133  continue;
134 
135  dom_int position = 0;
136  BOOST_FOREACH(dom_int el, rankIndices) {
137  if (el == x)
138  break;
139  if (getOrbitRank(el) == rank)
140  ++position;
141  }
142 
143  if (expectedPosition[rank] != position)
144  return false;
145 
146  ++expectedPosition[rank];
147  }
148 
149  return true;
150 }
151 
152 inline int AbstractSymmetricProduct::getOrbitRank(dom_int x) const {
153  if (m_indicesReverse.empty()) {
154  if (m_indices.empty())
155  return -1;
156 
157  dom_int rank = 0;
158  BOOST_FOREACH(const std::set<dom_int>& orb, m_indices) {
159  BOOST_FOREACH(dom_int el, orb) {
160  m_indicesReverse[el] = rank;
161  }
162  ++rank;
163  }
164  }
165 
166  std::map<dom_int, dom_int>::const_iterator pos = m_indicesReverse.find(x);
167  if (pos == m_indicesReverse.end())
168  return -1;
169 
170  return (*pos).second;
171 }
172 
173 } // end NS
174 
175 #endif
virtual AbstractGroupType type() const
implementation type of this abstract class
Definition: abstract_symmetric_product.h:68
virtual bool isLexMinSet(const std::vector< dom_int > &setIndices, const std::vector< dom_int > &rankIndices) const
checks whether a set is lexicographically minimal with respect to a given ordering of indices ...
Definition: abstract_symmetric_product.h:125
AbstractSymmetricProduct(InputIterator begin, InputIterator end)
constructor
Definition: abstract_symmetric_product.h:55
std::list< std::set< dom_int > > OrbitList
typedef for a list of orbits, each of which is a set
Definition: abstract_permutation_group.h:74
virtual OrbitList * orbits() const
computes all orbits
Definition: abstract_symmetric_product.h:109
virtual void transversalSizes(std::vector< unsigned long > &sizes) const
fills a list with sizes of transversals along a stabilizer chain
Definition: abstract_symmetric_product.h:82
A high level interface implementing a direct product of symmetric groups.
Definition: abstract_symmetric_product.h:44
stores an orbit in a sorted list
Definition: orbit_list.h:42
A high level interface for a permutation group.
Definition: abstract_permutation_group.h:54
Definition: abstract_bsgs.h:49
virtual AbstractPermutationGroup * setStabilizer(const std::vector< dom_int > &s) const
computes the stabilizer of a set
Definition: abstract_symmetric_product.h:91