permlib  0.2.9
Library for permutation computations
product_replacement_generator.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 PRODUCTREPLACEMENTGENERATOR_H
34 #define PRODUCTREPLACEMENTGENERATOR_H
35 
36 #include <permlib/generator/random_generator.h>
37 
38 #include <vector>
39 #include <boost/iterator/indirect_iterator.hpp>
40 
41 namespace permlib {
42 
44 template <class PERM>
46 public:
48 
52  template <class InputIterator>
53  ProductReplacementGenerator(const unsigned int n, InputIterator generatorsBegin, InputIterator generatorsEnd);
54 
55  virtual PERM next();
56 private:
57  std::vector<PERM> m_generators;
58  const unsigned int m_n;
59 };
60 
61 //
62 // ---- IMPLEMENTATION
63 //
64 
65 template <class PERM>
66 template <class InputIterator>
67 ProductReplacementGenerator<PERM>::ProductReplacementGenerator(const unsigned int n, InputIterator generatorsBegin, InputIterator generatorsEnd)
68  : m_generators(boost::indirect_iterator<InputIterator, PERM>(generatorsBegin),
69  boost::indirect_iterator<InputIterator, PERM>(generatorsEnd)),
70  m_n(n)
71 {
72  const unsigned int additionalElements = 10;
73  const unsigned int oldSize = m_generators.size();
74  const unsigned int replacementRounds = std::max(oldSize * 10, static_cast<unsigned int>(100));
75  if (oldSize == 0)
76  return;
77 
78  m_generators.reserve(oldSize + additionalElements + 1);
79  for (unsigned int i = 0; i < additionalElements; ++i) {
80  m_generators.push_back(m_generators[randomInt(oldSize)]);
81  }
82  m_generators.push_back(PERM(m_generators[0].size()));
83 
84  for (unsigned int k = 0; k < replacementRounds; ++k) {
85  next();
86  }
87 }
88 
89 template <class PERM>
91  if (m_generators.size() == 0) {
92  return PERM(m_n);
93  }
94 
95  unsigned int i = randomInt(m_generators.size() - 1);
96  unsigned int j = randomInt(m_generators.size() - 2);
97  if (j >= i) ++j;
98  switch (randomInt(4)) {
99  case 0:
100  m_generators[i] *= m_generators[j]; break;
101  case 1:
102  m_generators[i] *= ~m_generators[j]; break;
103  case 2:
104  m_generators[i] ^= m_generators[j]; break;
105  case 3:
106  m_generators[i] ^= ~m_generators[j]; break;
107  }
108  m_generators[m_generators.size()-1] *= m_generators[i];
109  return m_generators[m_generators.size()-1];
110 }
111 
112 }
113 
114 #endif // -- PRODUCTREPLACEMENTGENERATOR_H
ProductReplacementGenerator(const unsigned int n, InputIterator generatorsBegin, InputIterator generatorsEnd)
initializes class with group generators
Definition: product_replacement_generator.h:67
abstract base class for random group element generators
Definition: random_generator.h:42
virtual PERM next()
generates an element
Definition: product_replacement_generator.h:90
generates nearly-uniformly distributed random group elements using the product replacement algorithm ...
Definition: product_replacement_generator.h:45
Definition: abstract_bsgs.h:49