permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
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
41namespace permlib {
42
44
51template<class PERM>
52struct SymmetricGroup : public BSGSCore<PERM, SymmetricGroupTransversal<PERM> > {
54 explicit SymmetricGroup(unsigned int n);
56 SymmetricGroup(const SymmetricGroup<PERM>& symGroup);
59
62
63 virtual bool isSymmetricGroup() const { return true; }
64private:
65 void copy(const SymmetricGroup<PERM>& symGroup);
66};
67
68template<class PERM>
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
85template<class PERM>
86inline 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
101template<class PERM>
103 : BSGSCore<PERM,TRANS>(-symGroup.n, symGroup.n, symGroup.n)
104{
105 copy(symGroup);
106}
107
108template<class PERM>
110{
111 BOOST_ASSERT(symGroup.n == this->n);
112
113 BSGSCore<PERM,TRANS>::n = symGroup.n;
115 copy(symGroup);
116 return *this;
117}
118
119}
120
121
122#endif // SYMMETRICGROUP_H_
transversal of a symmetric group
Definition: symmetric_group_transversal.h:45
core data of a base and strong generating set (BSGS)
Definition: bsgs_core.h:42
dom_int n
degree of group
Definition: bsgs_core.h:61
std::vector< dom_int > B
base
Definition: bsgs_core.h:55
int m_id
id of this BSGS instance
Definition: bsgs_core.h:81
representation of a symmetric group
Definition: symmetric_group.h:52
virtual bool isSymmetricGroup() const
true if this structure represents a symmetric group
Definition: symmetric_group.h:63
SymmetricGroup(unsigned int n)
constructs a symmetric group of degree n
Definition: symmetric_group.h:69
SymmetricGroup & operator=(const SymmetricGroup< PERM > &symGroup)
assignment operator
Definition: symmetric_group.h:109
SymmetricGroupTransversal< PERM > TRANS
transversal type used for the BSGS representation
Definition: symmetric_group.h:61