permlib 0.2.9
Library for permutation computations
group_type.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#ifndef GROUP_TYPE_H_
33#define GROUP_TYPE_H_
34
35#include <cstring>
36
37namespace permlib {
38
40class GroupType {
41public:
43 enum Type {
44 None,
45 Trivial,
46 Named,
47 Anonymous,
48 WreathSymmetric,
49 DirectProduct
50 };
51
53 void writeToStream(std::ostream& o) const {
54 if (!m_naturalAction)
55 o << "ISO( ";
56 this->writeTypeToStream(o);
57 if (!m_naturalAction)
58 o << " , " << m_realDegree << " )";
59 }
60
62 unsigned int realDegree() const { return m_realDegree; }
64
67 bool isNaturalAction() const { return m_naturalAction; }
69 Type type() const { return m_type; }
70
72 bool equals(const GroupType* type_) const {
73 if (this->m_type != type_->m_type)
74 return false;
75 if (this->m_realDegree != type_->m_realDegree)
76 return false;
77 if (this->m_naturalAction != type_->m_naturalAction)
78 return false;
79 return this->equalsType(type_);
80 }
81
83 void setNonNaturalAction(unsigned int realDegree_) {
84 m_realDegree = realDegree_;
85 m_naturalAction = false;
86 }
87
89 virtual ~GroupType() { }
90protected:
94 unsigned int m_realDegree;
97
99 GroupType(Type type_, unsigned int realDegree_, bool naturalAction)
100 : m_type(type_), m_realDegree(realDegree_), m_naturalAction(naturalAction) { }
101
103
107 virtual bool equalsType(const GroupType* type_) const { return false; }
109 virtual void writeTypeToStream(std::ostream& o) const = 0;
110};
111
112
115public:
119 TrivialGroupType(unsigned int realDegree_) : GroupType(Trivial, realDegree_, true) { }
120
121 virtual void writeTypeToStream(std::ostream& o) const {
122 o << "Trivial(" << m_realDegree << ")";
123 }
124protected:
125 virtual bool equalsType(const GroupType* type_) const { return true; }
126};
127
128
130template<class IntegerType = boost::uint64_t>
132public:
137 AnonymousGroupType(unsigned int realDegree_, IntegerType order_ = 0)
138 : GroupType(Anonymous, realDegree_, true), m_order(order_) { }
139
140 virtual void writeTypeToStream(std::ostream& o) const {
141 if (m_order)
142 o << "anonymous(" << m_realDegree << ", " << m_order << ")";
143 else
144 o << "anonymous(" << m_realDegree << ")";
145 }
146protected:
147 IntegerType m_order;
148
149 virtual bool equalsType(const GroupType* type_) const {
150 // we can never know if two anonymous groups are equal without digging deeper
151 return false;
152 }
153};
154
155
157class NamedGroupType : public GroupType {
158public:
159 virtual void writeTypeToStream(std::ostream& o) const {
160 o << m_name << "_" << m_typeDegree;
161 }
162
164 const char* name() const { return m_name; }
166 unsigned int typeDegree() const { return m_typeDegree; }
167protected:
168 const char* m_name;
169 unsigned int m_typeDegree;
170
176 NamedGroupType(const char* name_, unsigned int typeDegree_, unsigned int realDegree_)
177 : GroupType(Named, realDegree_, typeDegree_ == realDegree_), m_name(name_), m_typeDegree(typeDegree_) { }
178
179 virtual bool equalsType(const GroupType* type_) const {
180 const NamedGroupType* namedType = dynamic_cast<const NamedGroupType*>(type_);
181 return namedType->m_typeDegree == this->m_typeDegree && std::strcmp(namedType->m_name, this->m_name) == 0;
182 }
183};
184
185
188public:
193 SymmetricGroupType(unsigned int typeDegree_, unsigned int realDegree_)
194 : NamedGroupType("S", typeDegree_, realDegree_) { }
195};
196
197
200public:
205 AlternatingGroupType(unsigned int typeDegree_, unsigned int realDegree_)
206 : NamedGroupType("A", typeDegree_, realDegree_) { }
207};
208
209
212public:
217 CyclicGroupType(unsigned int typeDegree_, unsigned int realDegree_)
218 : NamedGroupType("C", typeDegree_, realDegree_) { }
219};
220
221
223
227public:
228 WreathSymmetricGroupType(unsigned int degreeG_, unsigned int degreeH_, unsigned int realDegree_)
229 : GroupType(WreathSymmetric, realDegree_, realDegree_ == degreeG_ * degreeH_), m_degreeG(degreeG_), m_degreeH(degreeH_) { }
230
231 virtual void writeTypeToStream(std::ostream& o) const {
232 o << "S_" << m_degreeG << " wr S_" << m_degreeH;
233 }
234
235 unsigned int degreeG() const { return m_degreeG; }
236 unsigned int degreeH() const { return m_degreeH; }
237protected:
238 unsigned int m_degreeG;
239 unsigned int m_degreeH;
240
241 virtual bool equalsType(const GroupType* type_) const {
242 const WreathSymmetricGroupType* wreathType = dynamic_cast<const WreathSymmetricGroupType*>(type_);
243 return wreathType->m_degreeG == m_degreeG && wreathType->m_degreeH == m_degreeH;
244 }
245};
246
249public:
255 DirectProductGroupType(const GroupType* type1, const GroupType* type2, unsigned int realDegree_)
256 : GroupType(DirectProduct, realDegree_, realDegree_ == type1->realDegree() + type2->realDegree()), m_components(2)
257 {
258 m_components[0] = GroupTypePtr(type1);
259 m_components[1] = GroupTypePtr(type2);
260 }
261
262 virtual void writeTypeToStream(std::ostream& o) const {
263 for (unsigned int i = 0; i < m_components.size(); ++i) {
264 if (i > 0)
265 o << " x ";
266 m_components[i]->writeToStream(o);
267 }
268 }
269
270protected:
271 typedef boost::shared_ptr<const GroupType> GroupTypePtr;
272 std::vector<GroupTypePtr> m_components;
273
274 virtual bool equalsType(const GroupType* type_) const {
275 const DirectProductGroupType* directType = dynamic_cast<const DirectProductGroupType*>(type_);
276 if (m_components.size() != directType->m_components.size())
277 return false;
278 std::vector<GroupTypePtr>::const_iterator itMe = m_components.begin();
279 std::vector<GroupTypePtr>::const_iterator itOther = directType->m_components.begin();
280 while (itMe != m_components.end()) {
281 if ( ! (*itMe)->equals((*itOther).get()) )
282 return false;
283 ++itMe;
284 ++itOther;
285 }
286 return true;
287 }
288};
289
290}
291
292#endif
Group type for alternating groups.
Definition: group_type.h:199
AlternatingGroupType(unsigned int typeDegree_, unsigned int realDegree_)
Definition: group_type.h:205
Group type for a permutation group whose type could not be determined.
Definition: group_type.h:131
virtual bool equalsType(const GroupType *type_) const
checks if two group types represent the same permutation group
Definition: group_type.h:149
virtual void writeTypeToStream(std::ostream &o) const
writes type specific string to output stream
Definition: group_type.h:140
AnonymousGroupType(unsigned int realDegree_, IntegerType order_=0)
Definition: group_type.h:137
Group type for cyclic groups.
Definition: group_type.h:211
CyclicGroupType(unsigned int typeDegree_, unsigned int realDegree_)
Definition: group_type.h:217
Group type for a direct product of two groups.
Definition: group_type.h:248
virtual void writeTypeToStream(std::ostream &o) const
writes type specific string to output stream
Definition: group_type.h:262
virtual bool equalsType(const GroupType *type_) const
checks if two group types represent the same permutation group
Definition: group_type.h:274
DirectProductGroupType(const GroupType *type1, const GroupType *type2, unsigned int realDegree_)
Definition: group_type.h:255
abstract base class for permutation group types
Definition: group_type.h:40
unsigned int m_realDegree
degree of the permutation group
Definition: group_type.h:94
GroupType(Type type_, unsigned int realDegree_, bool naturalAction)
protected constructor
Definition: group_type.h:99
bool m_naturalAction
stores whether action is natural
Definition: group_type.h:96
bool equals(const GroupType *type_) const
checks if two group types represent the same permutation group
Definition: group_type.h:72
void writeToStream(std::ostream &o) const
writes a human readable identifier to the given output stream
Definition: group_type.h:53
bool isNaturalAction() const
returns true iff action is natural
Definition: group_type.h:67
Type
types for which an implementation of GroupType exists
Definition: group_type.h:43
virtual void writeTypeToStream(std::ostream &o) const =0
writes type specific string to output stream
virtual ~GroupType()
destructor
Definition: group_type.h:89
unsigned int realDegree() const
the degree of the group as permutation group
Definition: group_type.h:62
Type type() const
the type of this the group
Definition: group_type.h:69
virtual bool equalsType(const GroupType *type_) const
checks if two group types represent the same permutation group
Definition: group_type.h:107
void setNonNaturalAction(unsigned int realDegree_)
stores the information that this group acts non-naturally on realDegree many elements
Definition: group_type.h:83
Type m_type
group type
Definition: group_type.h:92
abstract base class for named groups (such as cyclic and symmetric groups)
Definition: group_type.h:157
virtual bool equalsType(const GroupType *type_) const
checks if two group types represent the same permutation group
Definition: group_type.h:179
virtual void writeTypeToStream(std::ostream &o) const
writes type specific string to output stream
Definition: group_type.h:159
NamedGroupType(const char *name_, unsigned int typeDegree_, unsigned int realDegree_)
Definition: group_type.h:176
const char * name() const
the name of the group
Definition: group_type.h:164
unsigned int typeDegree() const
the degree of the named group to which the real action is isomorphic to
Definition: group_type.h:166
Group type for symmetric groups.
Definition: group_type.h:187
SymmetricGroupType(unsigned int typeDegree_, unsigned int realDegree_)
Definition: group_type.h:193
Group type for a trivial permutation group.
Definition: group_type.h:114
virtual void writeTypeToStream(std::ostream &o) const
writes type specific string to output stream
Definition: group_type.h:121
virtual bool equalsType(const GroupType *type_) const
checks if two group types represent the same permutation group
Definition: group_type.h:125
TrivialGroupType(unsigned int realDegree_)
Definition: group_type.h:119
Group type for a wreath product of symmetric groups.
Definition: group_type.h:226
virtual void writeTypeToStream(std::ostream &o) const
writes type specific string to output stream
Definition: group_type.h:231
virtual bool equalsType(const GroupType *type_) const
checks if two group types represent the same permutation group
Definition: group_type.h:241