permlib  0.2.9
Library for permutation computations
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 
38 namespace permlib {
39 
41 template<class PERM, class TRANS, class BASETRANSPOSE>
42 class SimpleBaseChange : public BaseChange<PERM,TRANS> {
43 public:
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 
56 template<class PERM, class TRANS, class BASETRANSPOSE>
58  : BaseChange<PERM,TRANS>()
59 { }
60 
61 template<class PERM, class TRANS, class BASETRANSPOSE>
62 template<class InputIterator>
63 void 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);
99 
100  BOOST_ASSERT(origOrder == bsgs.order());
101 }
102 
103 }
104 
105 #endif // -- SIMPLEBASECHANGE_H_
unsigned int insertRedundantBasePoint(unsigned int beta, unsigned int minPos=0)
inserts a redundant base beta
Definition: bsgs.h:421
abstract base class for base change algorithms
Definition: base_change.h:46
SimpleBaseChange(const BSGS< PERM, TRANS > &)
constructor
Definition: simple_base_change.h:57
Integer order() const
order of the group
Definition: bsgs.h:406
void stripRedundantBasePoints(int minPos=0)
strips redundant base points from the end to the minPos-th base element
Definition: bsgs.h:436
std::vector< dom_int > B
base
Definition: bsgs_core.h:55
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
base change by a sequence of point insertions and transpositions
Definition: simple_base_change.h:42
unsigned int m_statScheierGeneratorsConsidered
nuber of Schreier generators considered in transposition since construction
Definition: base_change.h:55
Represents a base and strong generating set (BSGS)
Definition: bsgs.h:58
Definition: abstract_bsgs.h:49