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 PARTITION_H_ 00034 #define PARTITION_H_ 00035 00036 #include <algorithm> 00037 #include <list> 00038 #include <boost/foreach.hpp> 00039 #include <boost/dynamic_bitset.hpp> 00040 00041 namespace permlib { 00042 namespace partition { 00043 00044 template<class T> 00045 class BacktrackRefinement; 00046 00048 class Partition { 00049 public: 00051 explicit Partition(unsigned long n); 00052 00054 00061 template<class ForwardIterator> 00062 bool intersect(ForwardIterator begin, ForwardIterator end, unsigned int j); 00064 bool undoIntersection(); 00065 00068 template<class ForwardIterator> 00069 bool intersects(ForwardIterator begin, ForwardIterator end, unsigned int j) const; 00070 00071 typedef std::vector<unsigned int> vector_t; 00073 unsigned int fixPointsSize() const; 00075 vector_t::const_iterator fixPointsBegin() const; 00077 vector_t::const_iterator fixPointsEnd() const; 00079 unsigned long cells() const; 00081 unsigned long cellSize(unsigned int c) const; 00082 00083 typedef vector_t::const_iterator CellIt; 00084 00085 CellIt cellBegin(unsigned long cell) const { 00086 BOOST_ASSERT(cell < cells()); 00087 return partition.begin() + partitionCellBorder[cell]; 00088 } 00089 00090 CellIt cellEnd(unsigned long cell) const { 00091 BOOST_ASSERT(cell < cells()); 00092 return partition.begin() + partitionCellBorder[cell] + partitionCellLength[cell]; 00093 } 00094 private: 00095 explicit Partition(unsigned long n, bool); 00096 00097 vector_t partition; 00098 vector_t partitionCellBorder; 00099 vector_t partitionCellLength; 00100 vector_t partitionCellOf; 00102 vector_t m_newCell; 00103 00105 unsigned int cellCounter; 00106 00109 vector_t fix; 00111 unsigned int fixCounter; 00112 00113 friend std::ostream& operator<<(std::ostream& out, const Partition& p); 00114 00115 template<class T> 00116 friend class BacktrackRefinement; 00117 }; 00118 00119 inline std::ostream& operator<<(std::ostream& out, const Partition& p) { 00120 out << "["; 00121 Partition::vector_t::const_iterator border = p.partitionCellBorder.begin(); 00122 Partition::vector_t::const_iterator length = p.partitionCellLength.begin(); 00123 for (unsigned int j = 0; j < p.cellCounter; ++j) { 00124 for (unsigned int i = *border; i < *border + *length; ++i) { 00125 out << (p.partition[i] + 1) << " "; 00126 } 00127 out << "| "; 00128 ++border; 00129 ++length; 00130 } 00131 out << "]|("; 00132 int countFix = p.fixCounter; 00133 BOOST_FOREACH(unsigned long alpha, p.fix) { 00134 if (--countFix < 0) 00135 break; 00136 out << (alpha+1) << ","; 00137 } 00138 out << ")"; 00139 return out; 00140 } 00141 00142 inline Partition::Partition(unsigned long n) 00143 : partition(n), partitionCellBorder(n), partitionCellLength(n), partitionCellOf(n), m_newCell(n), cellCounter(1), fix(n), fixCounter(0) 00144 { 00145 for (unsigned int i=0; i<n; ++i) { 00146 partition[i] = i; 00147 // partitionCellOf is already zero 00148 } 00149 partitionCellBorder[0] = 0; 00150 partitionCellLength[0] = n; 00151 } 00152 00153 inline Partition::Partition(unsigned long n, bool) 00154 : partition(n), partitionCellBorder(n), partitionCellLength(n), partitionCellOf(n), m_newCell(n), cellCounter(0), fix(n), fixCounter(0) 00155 { } 00156 00157 inline unsigned long Partition::cells() const { 00158 return cellCounter; 00159 } 00160 00161 inline unsigned int Partition::fixPointsSize() const { 00162 return fixCounter; 00163 } 00164 inline Partition::vector_t::const_iterator Partition::fixPointsBegin() const { 00165 return fix.begin(); 00166 } 00167 inline Partition::vector_t::const_iterator Partition::fixPointsEnd() const { 00168 return fix.begin() + fixCounter; 00169 } 00170 inline unsigned long Partition::cellSize(unsigned int c) const { 00171 return partitionCellLength[c]; 00172 } 00173 00174 template<class ForwardIterator> 00175 inline bool Partition::intersects(ForwardIterator begin, ForwardIterator end, unsigned int j) const { 00176 while (begin != end) { 00177 //std::cout << " B " << *begin << " < " << partitionCellOf[*begin] << " < " << j << std::endl; 00178 if (partitionCellOf[*begin++] == j) 00179 return true; 00180 } 00181 return false; 00182 } 00183 00185 template<class ForwardIterator> 00186 inline bool Partition::intersect(ForwardIterator otherCellBegin, ForwardIterator otherCellEnd, unsigned int j) { 00187 if (!intersects(otherCellBegin, otherCellEnd, j)) 00188 return false; 00189 00190 vector_t& newCell = m_newCell; 00191 00192 ForwardIterator otherCellIt = otherCellBegin; 00193 vector_t::iterator cellIt; 00194 vector_t::reverse_iterator newCellIt; 00195 vector_t::reverse_iterator newCellBeginIt; 00196 vector_t::iterator newCell2It; 00197 vector_t::iterator borderIt; 00198 bool createdNewCell = false; 00199 const unsigned int partitionCellSize = partitionCellLength[j]; 00200 if (j >= cellCounter) 00201 return false; 00202 if (partitionCellSize <= 1) 00203 return false; 00204 vector_t::iterator cellBeginIt = partition.begin() + partitionCellBorder[j]; 00205 vector_t::iterator cellEndIt = partition.begin() + (partitionCellBorder[j] + partitionCellLength[j]); 00206 //print_iterable(cellBeginIt, cellEndIt, 1, " ^ cell"); 00207 newCellBeginIt = newCell.rbegin() + (partition.size() - partitionCellSize); 00208 newCellIt = newCellBeginIt; 00209 newCell2It = newCell.begin(); 00210 unsigned int newCellCounter = 0; 00211 00212 for (cellIt = cellBeginIt; cellIt != cellEndIt; ++cellIt) { 00213 while (otherCellIt != otherCellEnd && *otherCellIt < *cellIt) { 00214 ++otherCellIt; 00215 } 00216 if (otherCellIt != otherCellEnd && *cellIt == *otherCellIt) { 00217 *newCell2It = *cellIt; 00218 ++newCell2It; 00219 if (newCellCounter == 0) { 00220 /*std::cout << "copy into new cell "; 00221 print_iterable(partition.begin() + borderLo, cellIt, 1); 00222 std::cout << std::endl;*/ 00223 newCellIt = std::copy(cellBeginIt, cellIt, newCellIt); 00224 } 00225 ++newCellCounter; 00226 } else if (newCellCounter) { 00227 *newCellIt = *cellIt; 00228 ++newCellIt; 00229 } 00230 } 00231 00232 if (newCellCounter > 0 && newCellCounter < partitionCellSize) { 00233 std::reverse(newCellBeginIt, newCellIt); 00234 std::copy(newCell.begin(), newCell.begin() + partitionCellSize, cellBeginIt); 00235 /*std::cout << "new cell[" << partitionCellSize << "] = "; 00236 print_iterable(newCell.begin(), newCell.begin() + partitionCellSize, 1); 00237 std::cout << std::endl;*/ 00238 vector_t::iterator fixIt = fix.begin() + fixCounter; 00239 00240 if (newCellCounter == 1) { 00241 *fixIt = newCell[0]; 00242 ++fixIt; 00243 ++fixCounter; 00244 } 00245 if (newCellCounter == partitionCellSize - 1) { 00246 *fixIt = newCell[partitionCellSize - 1]; 00247 ++fixIt; 00248 ++fixCounter; 00249 } 00250 00251 /* 00252 for (unsigned int i = partitionCellBorder[j]; i < partitionCellBorder[j] + partitionCellLength[j]; ++i) { 00253 std::cout << partition[i]+1 << " "; 00254 } 00255 std::cout << std::endl; 00256 std::cout << "new cell counter " << newCellCounter << std::endl; 00257 */ 00258 00259 partitionCellLength[j] = newCellCounter; 00260 00261 //std::cout << "cellCounter " << cellCounter << std::endl; 00262 partitionCellBorder[cellCounter] = partitionCellBorder[j] + newCellCounter; 00263 partitionCellLength[cellCounter] = partitionCellSize - newCellCounter; 00264 for (unsigned int i = partitionCellBorder[cellCounter]; i < partitionCellBorder[j] + partitionCellSize; ++i) { 00265 BOOST_ASSERT( i < partition.size() ); 00266 BOOST_ASSERT( partition[i] < partitionCellOf.size() ); 00267 partitionCellOf[partition[i]] = cellCounter; 00268 } 00269 ++cellCounter; 00270 00271 createdNewCell = true; 00272 } 00273 00274 return createdNewCell; 00275 } 00276 00277 inline bool Partition::undoIntersection() { 00278 if (partitionCellBorder[cellCounter-1] < 1) 00279 return false; 00280 --cellCounter; 00281 unsigned int splitFromCellNumber = partitionCellOf[ partition[partitionCellBorder[cellCounter] - 1] ]; 00282 00283 BOOST_ASSERT(partitionCellBorder[splitFromCellNumber] < partitionCellBorder[cellCounter]); 00284 BOOST_ASSERT(partitionCellLength[cellCounter] > 0 ); 00285 //std::cout << "split from " << splitFromCellNumber << std::endl; 00286 //std::cout << "merge " << partitionCellBorder[splitFromCellNumber] << " " << partitionCellBorder[cellCounter] << " " << (partitionCellBorder[cellCounter] + partitionCellLength[cellCounter]) << std::endl; 00287 00288 for (unsigned int i=partitionCellBorder[cellCounter]; i<partitionCellBorder[cellCounter] + partitionCellLength[cellCounter]; ++i) { 00289 partitionCellOf[partition[i]] = splitFromCellNumber; 00290 } 00291 std::inplace_merge(partition.begin() + partitionCellBorder[splitFromCellNumber], 00292 partition.begin() + partitionCellBorder[cellCounter], 00293 partition.begin() + (partitionCellBorder[cellCounter] + partitionCellLength[cellCounter])); 00294 00295 00296 if (partitionCellLength[cellCounter] == 1) { 00297 --fixCounter; 00298 fix[fixCounter] = 0; 00299 } 00300 if (partitionCellLength[splitFromCellNumber] == 1) { 00301 --fixCounter; 00302 fix[fixCounter] = 0; 00303 } 00304 00305 partitionCellLength[splitFromCellNumber] += partitionCellLength[cellCounter]; 00306 00307 partitionCellLength[cellCounter] = 0; 00308 partitionCellBorder[cellCounter] = 0; 00309 00310 return true; 00311 } 00312 00313 } 00314 } 00315 00316 #endif // -- PARTITION_H_