permlib
0.2.6
Library for permutation computations
|
00001 // --------------------------------------------------------------------------- 00002 // 00003 // This file is part of PermLib. 00004 // 00005 // Copyright (c) 2009-2011 Thomas Rehn <thomas@carmen76.de> 00006 // All rights reserved. 00007 // 00008 // Redistribution and use in source and binary forms, with or without 00009 // modification, are permitted provided that the following conditions 00010 // are met: 00011 // 1. Redistributions of source code must retain the above copyright 00012 // notice, this list of conditions and the following disclaimer. 00013 // 2. Redistributions in binary form must reproduce the above copyright 00014 // notice, this list of conditions and the following disclaimer in the 00015 // documentation and/or other materials provided with the distribution. 00016 // 3. The name of the author may not be used to endorse or promote products 00017 // derived from this software without specific prior written permission. 00018 // 00019 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 00020 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 00021 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 00022 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 00023 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 00024 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 00025 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 00026 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 00027 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 00028 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00029 // 00030 // --------------------------------------------------------------------------- 00031 00032 00033 #ifndef PRODUCTREPLACEMENTGENERATOR_H 00034 #define PRODUCTREPLACEMENTGENERATOR_H 00035 00036 #include <permlib/generator/random_generator.h> 00037 00038 #include <vector> 00039 #include <boost/iterator/indirect_iterator.hpp> 00040 00041 namespace permlib { 00042 00044 template <class PERM> 00045 class ProductReplacementGenerator : public RandomGenerator<PERM> { 00046 public: 00048 00052 template <class InputIterator> 00053 ProductReplacementGenerator(const unsigned int n, InputIterator generatorsBegin, InputIterator generatorsEnd); 00054 00055 virtual PERM next(); 00056 private: 00057 std::vector<PERM> m_generators; 00058 const unsigned int m_n; 00059 }; 00060 00061 // 00062 // ---- IMPLEMENTATION 00063 // 00064 00065 template <class PERM> 00066 template <class InputIterator> 00067 ProductReplacementGenerator<PERM>::ProductReplacementGenerator(const unsigned int n, InputIterator generatorsBegin, InputIterator generatorsEnd) 00068 : m_generators(boost::indirect_iterator<InputIterator, PERM>(generatorsBegin), 00069 boost::indirect_iterator<InputIterator, PERM>(generatorsEnd)), 00070 m_n(n) 00071 { 00072 const unsigned int additionalElements = 10; 00073 const unsigned int oldSize = m_generators.size(); 00074 const unsigned int replacementRounds = std::max(oldSize * 10, static_cast<unsigned int>(100)); 00075 if (oldSize == 0) 00076 return; 00077 00078 m_generators.reserve(oldSize + additionalElements + 1); 00079 for (unsigned int i = 0; i < additionalElements; ++i) { 00080 m_generators.push_back(m_generators[randomInt(oldSize)]); 00081 } 00082 m_generators.push_back(PERM(m_generators[0].size())); 00083 00084 for (unsigned int k = 0; k < replacementRounds; ++k) { 00085 next(); 00086 } 00087 } 00088 00089 template <class PERM> 00090 PERM ProductReplacementGenerator<PERM>::next() { 00091 if (m_generators.size() == 0) { 00092 return PERM(m_n); 00093 } 00094 00095 unsigned int i = randomInt(m_generators.size() - 1); 00096 unsigned int j = randomInt(m_generators.size() - 2); 00097 if (j >= i) ++j; 00098 switch (randomInt(4)) { 00099 case 0: 00100 m_generators[i] *= m_generators[j]; break; 00101 case 1: 00102 m_generators[i] *= ~m_generators[j]; break; 00103 case 2: 00104 m_generators[i] ^= m_generators[j]; break; 00105 case 3: 00106 m_generators[i] ^= ~m_generators[j]; break; 00107 } 00108 m_generators[m_generators.size()-1] *= m_generators[i]; 00109 return m_generators[m_generators.size()-1]; 00110 } 00111 00112 } 00113 00114 #endif // -- PRODUCTREPLACEMENTGENERATOR_H