permlib  0.2.9
Library for permutation computations
symmetric_group.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 SYMMETRICGROUP_H_
34 #define SYMMETRICGROUP_H_
35 
36 #include <permlib/bsgs_core.h>
37 #include <permlib/transversal/symmetric_group_transversal.h>
38 
39 #include <boost/shared_ptr.hpp>
40 
41 namespace permlib {
42 
44 
51 template<class PERM>
52 struct SymmetricGroup : public BSGSCore<PERM, SymmetricGroupTransversal<PERM> > {
54  explicit SymmetricGroup(unsigned int n);
56  SymmetricGroup(const SymmetricGroup<PERM>& symGroup);
58  SymmetricGroup& operator=(const SymmetricGroup<PERM>& symGroup);
59 
62 
63  virtual bool isSymmetricGroup() const { return true; }
64 private:
65  void copy(const SymmetricGroup<PERM>& symGroup);
66 };
67 
68 template<class PERM>
69 inline SymmetricGroup<PERM>::SymmetricGroup(unsigned int n_)
70  : BSGSCore<PERM,TRANS>(-n_, n_, n_)
71 {
72  BOOST_ASSERT(this->n > 0);
73  BSGSCore<PERM,TRANS>::U.reserve(this->n);
74  for (unsigned int i = 0; i < this->n; ++i) {
75  BSGSCore<PERM,TRANS>::B[i] = this->n-1-i;
77  if (i < static_cast<unsigned int>(this->n-1)) {
78  boost::shared_ptr<PERM> gen(new PERM(this->n));
79  gen->setTransposition(i, i+1);
80  BSGSCore<PERM,TRANS>::S.push_back(gen);
81  }
82  }
83 }
84 
85 template<class PERM>
86 inline void SymmetricGroup<PERM>::copy(const SymmetricGroup<PERM>& symGroup)
87 {
88  const unsigned long& n2 = symGroup.n;
89  BSGSCore<PERM,TRANS>::U.reserve(n2);
90  for (unsigned int i = 0; i < n2; ++i) {
91  BSGSCore<PERM,TRANS>::B[i] = symGroup.B[i];
93  if (i < n2-1) {
94  boost::shared_ptr<PERM> gen(new PERM(n2));
95  gen->setTransposition(i, i+1);
96  BSGSCore<PERM,TRANS>::S.push_back(gen);
97  }
98  }
99 }
100 
101 template<class PERM>
103  : BSGSCore<PERM,TRANS>(-symGroup.n, symGroup.n, symGroup.n)
104 {
105  copy(symGroup);
106 }
107 
108 template<class PERM>
110 {
111  BOOST_ASSERT(symGroup.n == this->n);
112 
113  BSGSCore<PERM,TRANS>::n = symGroup.n;
114  BSGSCore<PERM,TRANS>::m_id = symGroup.m_id;
115  copy(symGroup);
116  return *this;
117 }
118 
119 }
120 
121 
122 #endif // SYMMETRICGROUP_H_
dom_int n
degree of group
Definition: bsgs_core.h:61
transversal of a symmetric group
Definition: symmetric_group_transversal.h:45
virtual bool isSymmetricGroup() const
true if this structure represents a symmetric group
Definition: symmetric_group.h:63
core data of a base and strong generating set (BSGS)
Definition: bsgs_core.h:42
SymmetricGroup(unsigned int n)
constructs a symmetric group of degree n
Definition: symmetric_group.h:69
representation of a symmetric group
Definition: conjugating_base_change.h:45
SymmetricGroupTransversal< PERM > TRANS
transversal type used for the BSGS representation
Definition: symmetric_group.h:61
SymmetricGroup & operator=(const SymmetricGroup< PERM > &symGroup)
assignment operator
Definition: symmetric_group.h:109
Definition: abstract_bsgs.h:49