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 BACKTRACKREFINEMENT_H_ 00034 #define BACKTRACKREFINEMENT_H_ 00035 00036 #include <permlib/search/partition/refinement.h> 00037 00038 #include <list> 00039 00040 namespace permlib { 00041 namespace partition { 00042 00044 template<class PERM> 00045 class BacktrackRefinement : public Refinement<PERM> { 00046 public: 00048 explicit BacktrackRefinement(unsigned long n); 00050 00054 BacktrackRefinement(unsigned long n, unsigned long alpha); 00055 00056 virtual unsigned int apply(Partition& pi) const; 00057 00059 unsigned long alpha() const; 00060 virtual void sort(const BaseSorterByReference& sorter, const Partition* pi); 00061 protected: 00062 virtual bool init(Partition& pi); 00063 private: 00064 unsigned long m_alpha; 00065 unsigned int m_cellElementIndex; 00066 unsigned int m_cellIndex; 00067 00068 typedef typename Refinement<PERM>::RefinementPtr RefinementPtr; 00069 00070 struct RefinementSorter : public std::binary_function<RefinementPtr, RefinementPtr, bool> { 00071 RefinementSorter(const BaseSorterByReference& sorter, const Partition* pi) : m_sorter(sorter), m_pi(pi) {} 00072 00073 bool operator()(RefinementPtr a, RefinementPtr b) const { 00074 BacktrackRefinement<PERM>* backtrackA = static_cast<BacktrackRefinement<PERM>*>(a.get()); 00075 BacktrackRefinement<PERM>* backtrackB = static_cast<BacktrackRefinement<PERM>*>(b.get()); 00076 if (m_pi) { 00077 return m_sorter(m_pi->partition[backtrackA->m_cellElementIndex], m_pi->partition[backtrackB->m_cellElementIndex]); 00078 } 00079 return m_sorter(backtrackA->m_alpha, backtrackB->m_alpha); 00080 } 00081 private: 00082 const BaseSorterByReference& m_sorter; 00083 const Partition* m_pi; 00084 }; 00085 00086 static const unsigned int overrideAlphaChoiceCellSizeRatio = 8; 00087 }; 00088 00089 template<class PERM> 00090 BacktrackRefinement<PERM>::BacktrackRefinement(unsigned long n) 00091 : Refinement<PERM>(n, Backtrack), m_alpha(-1), m_cellElementIndex(-1), m_cellIndex(-1) 00092 { } 00093 00094 template<class PERM> 00095 BacktrackRefinement<PERM>::BacktrackRefinement(unsigned long n, unsigned long alpha_) 00096 : Refinement<PERM>(n, Backtrack), m_alpha(alpha_), m_cellElementIndex(-1), m_cellIndex(-1) 00097 { } 00098 00099 template<class PERM> 00100 unsigned int BacktrackRefinement<PERM>::apply(Partition& pi) const { 00101 unsigned long singleCell[1]; 00102 singleCell[0] = pi.partition[m_cellElementIndex]; 00103 //singleCell[0] = t / m_alpha; 00104 //print_iterable(pi.partition.begin(), pi.partition.end(), 0, " partition pi"); 00105 PERMLIB_DEBUG(std::cout << " apply bt ref alpha =" << m_alpha << ", single cell = " << singleCell[0] << " @ " << m_cellIndex << "," << m_cellElementIndex << std::endl;) 00106 return pi.intersect(singleCell, singleCell+1, m_cellIndex); 00107 } 00108 00109 template<class PERM> 00110 unsigned long BacktrackRefinement<PERM>::alpha() const { 00111 return m_alpha; 00112 } 00113 00114 template<class PERM> 00115 void BacktrackRefinement<PERM>::sort(const BaseSorterByReference& sorter, const Partition* pi) { 00116 std::sort(Refinement<PERM>::m_backtrackRefinements.begin(), Refinement<PERM>::m_backtrackRefinements.end(), RefinementSorter(sorter, pi)); 00117 } 00118 00119 template<class PERM> 00120 bool BacktrackRefinement<PERM>::init(Partition& pi) { 00121 unsigned int minCellSize = pi.partition.size(); 00122 unsigned int minCell = 0; 00123 //std::cout << "m_alpha " << m_alpha << std::endl; 00124 00125 std::vector<unsigned int>::const_iterator length = pi.partitionCellLength.begin(); 00126 for (unsigned int j = 0; j < pi.cellCounter; ++j) { 00127 if (1 < *length && *length < minCellSize) { 00128 minCellSize = *length; 00129 minCell = j; 00130 } 00131 ++length; 00132 } 00133 if (m_alpha == static_cast<unsigned long>(-1)) { 00134 this->m_cellElementIndex = pi.partitionCellBorder[minCell]; 00135 this->m_alpha = pi.partition[pi.partitionCellBorder[minCell]]; 00136 } else { 00137 const unsigned int givenMinCell = pi.partitionCellOf[m_alpha]; 00138 const unsigned int givenMinCellSize = pi.partitionCellLength[givenMinCell]; 00139 if (1 < givenMinCellSize && givenMinCellSize <= overrideAlphaChoiceCellSizeRatio * minCellSize) { 00140 minCell = givenMinCell; 00141 minCellSize = givenMinCellSize; 00142 for (unsigned int j = pi.partitionCellBorder[minCell]; j < pi.partitionCellBorder[minCell] + pi.partitionCellLength[minCell]; ++j) { 00143 if (pi.partition[j] == m_alpha) { 00144 this->m_cellElementIndex = j; 00145 break; 00146 } 00147 } 00148 } else { 00149 this->m_cellElementIndex = pi.partitionCellBorder[minCell]; 00150 this->m_alpha = pi.partition[pi.partitionCellBorder[minCell]]; 00151 } 00152 } 00153 PERMLIB_DEBUG(std::cout << "minCellSize = " << minCellSize << std::endl;) 00154 00155 this->m_cellIndex = minCell; 00156 00157 Refinement<PERM>::m_backtrackRefinements.reserve(minCellSize); 00158 for (unsigned int i = pi.partitionCellBorder[minCell]; i < pi.partitionCellBorder[minCell] + minCellSize; ++i) { 00159 BacktrackRefinement<PERM>* br = new BacktrackRefinement<PERM>(Refinement<PERM>::m_n); 00160 br->m_cellElementIndex = i; 00161 br->m_cellIndex = minCell; 00162 br->m_alpha = pi.partition[i]; 00163 //print_iterable(pi.partition.begin(), pi.partition.end(), 0, " partition pi"); 00164 PERMLIB_DEBUG(std::cout << "PREP bt alpha " << br->m_alpha << " @ " << br->m_cellIndex << " // " << br->m_cellElementIndex << std::endl;) 00165 typename Refinement<PERM>::RefinementPtr ref(br); 00166 Refinement<PERM>::m_backtrackRefinements.push_back(ref); 00167 } 00168 00169 unsigned long singleCell[1]; 00170 singleCell[0] = this->m_alpha; 00171 //TODO: write special case function to handle singleCell intersection 00172 const bool inter __attribute__((unused)) = pi.intersect(singleCell, singleCell+1, m_cellIndex); 00173 BOOST_ASSERT(inter); 00174 00175 return true; 00176 } 00177 00178 } 00179 } 00180 00181 #endif // -- BACKTRACKREFINEMENT_H_