permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
partition.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 PARTITION_H_
34#define PARTITION_H_
35
36#include <algorithm>
37#include <list>
38#include <boost/foreach.hpp>
39#include <boost/dynamic_bitset.hpp>
40
41namespace permlib {
42namespace partition {
43
44template<class T>
45class BacktrackRefinement;
46
48class Partition {
49public:
51 explicit Partition(unsigned long n);
52
54
61 template<class ForwardIterator>
62 bool intersect(ForwardIterator begin, ForwardIterator end, unsigned int j);
64 bool undoIntersection();
65
68 template<class ForwardIterator>
69 bool intersects(ForwardIterator begin, ForwardIterator end, unsigned int j) const;
70
71 typedef std::vector<unsigned int> vector_t;
73 unsigned int fixPointsSize() const;
75 vector_t::const_iterator fixPointsBegin() const;
77 vector_t::const_iterator fixPointsEnd() const;
79 unsigned long cells() const;
81 unsigned long cellSize(unsigned int c) const;
82
83 typedef vector_t::const_iterator CellIt;
84
85 CellIt cellBegin(unsigned long cell) const {
86 BOOST_ASSERT(cell < cells());
87 return partition.begin() + partitionCellBorder[cell];
88 }
89
90 CellIt cellEnd(unsigned long cell) const {
91 BOOST_ASSERT(cell < cells());
92 return partition.begin() + partitionCellBorder[cell] + partitionCellLength[cell];
93 }
94private:
95 explicit Partition(unsigned long n, bool);
96
97 vector_t partition;
98 vector_t partitionCellBorder;
99 vector_t partitionCellLength;
100 vector_t partitionCellOf;
102 vector_t m_newCell;
103
105 unsigned int cellCounter;
106
109 vector_t fix;
111 unsigned int fixCounter;
112
113 friend std::ostream& operator<<(std::ostream& out, const Partition& p);
114
115 template<class T>
116 friend class BacktrackRefinement;
117};
118
119inline std::ostream& operator<<(std::ostream& out, const Partition& p) {
120 out << "[";
121 Partition::vector_t::const_iterator border = p.partitionCellBorder.begin();
122 Partition::vector_t::const_iterator length = p.partitionCellLength.begin();
123 for (unsigned int j = 0; j < p.cellCounter; ++j) {
124 for (unsigned int i = *border; i < *border + *length; ++i) {
125 out << (p.partition[i] + 1) << " ";
126 }
127 out << "| ";
128 ++border;
129 ++length;
130 }
131 out << "]|(";
132 int countFix = p.fixCounter;
133 BOOST_FOREACH(unsigned long alpha, p.fix) {
134 if (--countFix < 0)
135 break;
136 out << (alpha+1) << ",";
137 }
138 out << ")";
139 return out;
140}
141
142inline Partition::Partition(unsigned long n)
143 : partition(n), partitionCellBorder(n), partitionCellLength(n), partitionCellOf(n), m_newCell(n), cellCounter(1), fix(n), fixCounter(0)
144{
145 for (unsigned int i=0; i<n; ++i) {
146 partition[i] = i;
147 // partitionCellOf is already zero
148 }
149 partitionCellBorder[0] = 0;
150 partitionCellLength[0] = n;
151}
152
153inline Partition::Partition(unsigned long n, bool)
154 : partition(n), partitionCellBorder(n), partitionCellLength(n), partitionCellOf(n), m_newCell(n), cellCounter(0), fix(n), fixCounter(0)
155{ }
156
157inline unsigned long Partition::cells() const {
158 return cellCounter;
159}
160
161inline unsigned int Partition::fixPointsSize() const {
162 return fixCounter;
163}
164inline Partition::vector_t::const_iterator Partition::fixPointsBegin() const {
165 return fix.begin();
166}
167inline Partition::vector_t::const_iterator Partition::fixPointsEnd() const {
168 return fix.begin() + fixCounter;
169}
170inline unsigned long Partition::cellSize(unsigned int c) const {
171 return partitionCellLength[c];
172}
173
174template<class ForwardIterator>
175inline bool Partition::intersects(ForwardIterator begin, ForwardIterator end, unsigned int j) const {
176 while (begin != end) {
177 //std::cout << " B " << *begin << " < " << partitionCellOf[*begin] << " < " << j << std::endl;
178 if (partitionCellOf[*begin++] == j)
179 return true;
180 }
181 return false;
182}
183
185template<class ForwardIterator>
186inline bool Partition::intersect(ForwardIterator otherCellBegin, ForwardIterator otherCellEnd, unsigned int j) {
187 if (!intersects(otherCellBegin, otherCellEnd, j))
188 return false;
189
190 vector_t& newCell = m_newCell;
191
192 ForwardIterator otherCellIt = otherCellBegin;
193 vector_t::iterator cellIt;
194 vector_t::reverse_iterator newCellIt;
195 vector_t::reverse_iterator newCellBeginIt;
196 vector_t::iterator newCell2It;
197 vector_t::iterator borderIt;
198 bool createdNewCell = false;
199 const unsigned int partitionCellSize = partitionCellLength[j];
200 if (j >= cellCounter)
201 return false;
202 if (partitionCellSize <= 1)
203 return false;
204 vector_t::iterator cellBeginIt = partition.begin() + partitionCellBorder[j];
205 vector_t::iterator cellEndIt = partition.begin() + (partitionCellBorder[j] + partitionCellLength[j]);
206 //print_iterable(cellBeginIt, cellEndIt, 1, " ^ cell");
207 newCellBeginIt = newCell.rbegin() + (partition.size() - partitionCellSize);
208 newCellIt = newCellBeginIt;
209 newCell2It = newCell.begin();
210 unsigned int newCellCounter = 0;
211
212 for (cellIt = cellBeginIt; cellIt != cellEndIt; ++cellIt) {
213 while (otherCellIt != otherCellEnd && *otherCellIt < *cellIt) {
214 ++otherCellIt;
215 }
216 if (otherCellIt != otherCellEnd && *cellIt == *otherCellIt) {
217 *newCell2It = *cellIt;
218 ++newCell2It;
219 if (newCellCounter == 0) {
220 /*std::cout << "copy into new cell ";
221 print_iterable(partition.begin() + borderLo, cellIt, 1);
222 std::cout << std::endl;*/
223 newCellIt = std::copy(cellBeginIt, cellIt, newCellIt);
224 }
225 ++newCellCounter;
226 } else if (newCellCounter) {
227 *newCellIt = *cellIt;
228 ++newCellIt;
229 }
230 }
231
232 if (newCellCounter > 0 && newCellCounter < partitionCellSize) {
233 std::reverse(newCellBeginIt, newCellIt);
234 std::copy(newCell.begin(), newCell.begin() + partitionCellSize, cellBeginIt);
235 /*std::cout << "new cell[" << partitionCellSize << "] = ";
236 print_iterable(newCell.begin(), newCell.begin() + partitionCellSize, 1);
237 std::cout << std::endl;*/
238 vector_t::iterator fixIt = fix.begin() + fixCounter;
239
240 if (newCellCounter == 1) {
241 *fixIt = newCell[0];
242 ++fixIt;
243 ++fixCounter;
244 }
245 if (newCellCounter == partitionCellSize - 1) {
246 *fixIt = newCell[partitionCellSize - 1];
247 ++fixIt;
248 ++fixCounter;
249 }
250
251 /*
252 for (unsigned int i = partitionCellBorder[j]; i < partitionCellBorder[j] + partitionCellLength[j]; ++i) {
253 std::cout << partition[i]+1 << " ";
254 }
255 std::cout << std::endl;
256 std::cout << "new cell counter " << newCellCounter << std::endl;
257 */
258
259 partitionCellLength[j] = newCellCounter;
260
261 //std::cout << "cellCounter " << cellCounter << std::endl;
262 partitionCellBorder[cellCounter] = partitionCellBorder[j] + newCellCounter;
263 partitionCellLength[cellCounter] = partitionCellSize - newCellCounter;
264 for (unsigned int i = partitionCellBorder[cellCounter]; i < partitionCellBorder[j] + partitionCellSize; ++i) {
265 BOOST_ASSERT( i < partition.size() );
266 BOOST_ASSERT( partition[i] < partitionCellOf.size() );
267 partitionCellOf[partition[i]] = cellCounter;
268 }
269 ++cellCounter;
270
271 createdNewCell = true;
272 }
273
274 return createdNewCell;
275}
276
278 if (partitionCellBorder[cellCounter-1] < 1)
279 return false;
280 --cellCounter;
281 unsigned int splitFromCellNumber = partitionCellOf[ partition[partitionCellBorder[cellCounter] - 1] ];
282
283 BOOST_ASSERT(partitionCellBorder[splitFromCellNumber] < partitionCellBorder[cellCounter]);
284 BOOST_ASSERT(partitionCellLength[cellCounter] > 0 );
285 //std::cout << "split from " << splitFromCellNumber << std::endl;
286 //std::cout << "merge " << partitionCellBorder[splitFromCellNumber] << " " << partitionCellBorder[cellCounter] << " " << (partitionCellBorder[cellCounter] + partitionCellLength[cellCounter]) << std::endl;
287
288 for (unsigned int i=partitionCellBorder[cellCounter]; i<partitionCellBorder[cellCounter] + partitionCellLength[cellCounter]; ++i) {
289 partitionCellOf[partition[i]] = splitFromCellNumber;
290 }
291 std::inplace_merge(partition.begin() + partitionCellBorder[splitFromCellNumber],
292 partition.begin() + partitionCellBorder[cellCounter],
293 partition.begin() + (partitionCellBorder[cellCounter] + partitionCellLength[cellCounter]));
294
295
296 if (partitionCellLength[cellCounter] == 1) {
297 --fixCounter;
298 fix[fixCounter] = 0;
299 }
300 if (partitionCellLength[splitFromCellNumber] == 1) {
301 --fixCounter;
302 fix[fixCounter] = 0;
303 }
304
305 partitionCellLength[splitFromCellNumber] += partitionCellLength[cellCounter];
306
307 partitionCellLength[cellCounter] = 0;
308 partitionCellBorder[cellCounter] = 0;
309
310 return true;
311}
312
313}
314}
315
316#endif // -- PARTITION_H_
backtrack refinement
Definition: backtrack_refinement.h:45
partition
Definition: partition.h:48
unsigned long cellSize(unsigned int c) const
size of the c-th cell
Definition: partition.h:170
unsigned long cells() const
number of cells in this partition
Definition: partition.h:157
bool intersects(ForwardIterator begin, ForwardIterator end, unsigned int j) const
Definition: partition.h:175
vector_t::const_iterator fixPointsBegin() const
iterator to the begin of fix points
Definition: partition.h:164
bool undoIntersection()
reverts the last intersection if there is one
Definition: partition.h:277
bool intersect(ForwardIterator begin, ForwardIterator end, unsigned int j)
intersects the j-th cell of this partition with a given set
Definition: partition.h:186
Partition(unsigned long n)
constructs an empty partition of length n
Definition: partition.h:142
unsigned int fixPointsSize() const
number of fix points in this partition
Definition: partition.h:161
vector_t::const_iterator fixPointsEnd() const
iterator to the end of fix points
Definition: partition.h:167