permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
simple_base_change.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 SIMPLEBASECHANGE_H_
34#define SIMPLEBASECHANGE_H_
35
36#include <permlib/change/base_change.h>
37
38namespace permlib {
39
41template<class PERM, class TRANS, class BASETRANSPOSE>
42class SimpleBaseChange : public BaseChange<PERM,TRANS> {
43public:
45 explicit SimpleBaseChange(const BSGS<PERM,TRANS>&);
46
48 template <class InputIterator>
49 void change(BSGS<PERM,TRANS> &bsgs, InputIterator baseBegin, InputIterator baseEnd, bool skipRedundant = false) const;
50};
51
52//
53// ---- IMPLEMENTATION
54//
55
56template<class PERM, class TRANS, class BASETRANSPOSE>
60
61template<class PERM, class TRANS, class BASETRANSPOSE>
62template<class InputIterator>
63void SimpleBaseChange<PERM,TRANS,BASETRANSPOSE>::change(BSGS<PERM,TRANS> &bsgs, InputIterator baseBegin, InputIterator baseEnd, bool skipRedundant) const {
64 if (baseBegin == baseEnd)
65 return;
66
67 const unsigned long origOrder __attribute__((unused)) = bsgs.order();
68 BASETRANSPOSE trans;
69
70 unsigned int baseTargetPos = 0;
71 while (baseBegin != baseEnd && baseTargetPos < bsgs.B.size()) {
72 unsigned long alpha = *baseBegin;
73 unsigned long beta = bsgs.B[baseTargetPos];
74 const bool redundant = skipRedundant && this->isRedundant(bsgs, baseTargetPos, alpha);
75
76 if (!redundant && beta != alpha) {
77 unsigned int pos = bsgs.insertRedundantBasePoint(alpha);
78 for (; pos > baseTargetPos; --pos) {
79 trans.transpose(bsgs, pos-1);
81 }
82 }
83
84 ++baseBegin;
85 if (!redundant)
86 ++baseTargetPos;
87 }
88 // insert remaining base points
89 while (!skipRedundant && baseBegin != baseEnd) {
90 const unsigned long alpha = *baseBegin;
91 bsgs.insertRedundantBasePoint(alpha, baseTargetPos);
92
93 ++baseBegin;
94 ++baseTargetPos;
95 }
96
97 bsgs.stripRedundantBasePoints(baseTargetPos);
98 BaseChange<PERM,TRANS>::m_statScheierGeneratorsConsidered += trans.m_statScheierGeneratorsConsidered;
99
100 BOOST_ASSERT(origOrder == bsgs.order());
101}
102
103}
104
105#endif // -- SIMPLEBASECHANGE_H_
unsigned int m_statScheierGeneratorsConsidered
nuber of Schreier generators considered in transposition since construction
Definition base_change.h:55
bool isRedundant(const BSGSCore< PERM, TRANS > &bsgs, unsigned int baseTargetPos, unsigned long alpha) const
checks if insertion of a base point at given position is redundant
Definition base_change.h:67
unsigned int m_statTranspositions
nuber of base transpositions needed since construction
Definition base_change.h:52
BaseChange()
constructor
Definition base_change.h:49
void change(BSGS< PERM, TRANS > &bsgs, InputIterator baseBegin, InputIterator baseEnd, bool skipRedundant=false) const
changes base of bsgs so that it starts with the sequence given by baseBegin to baseEnd
Definition simple_base_change.h:63
SimpleBaseChange(const BSGS< PERM, TRANS > &)
constructor
Definition simple_base_change.h:57
std::vector< dom_int > B
base
Definition bsgs_core.h:55
Represents a base and strong generating set (BSGS)
Definition bsgs.h:89
unsigned int insertRedundantBasePoint(unsigned int beta, unsigned int minPos=0)
inserts a redundant base beta
Definition bsgs.h:422
void stripRedundantBasePoints(int minPos=0)
strips redundant base points from the end to the minPos-th base element
Definition bsgs.h:437
Integer order() const
order of the group
Definition bsgs.h:407