permlib  0.2.9
Library for permutation computations
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 
41 namespace permlib {
42 namespace partition {
43 
44 template<class T>
45 class BacktrackRefinement;
46 
48 class Partition {
49 public:
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  }
94 private:
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 
119 inline 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 
142 inline 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 
153 inline 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 
157 inline unsigned long Partition::cells() const {
158  return cellCounter;
159 }
160 
161 inline unsigned int Partition::fixPointsSize() const {
162  return fixCounter;
163 }
164 inline Partition::vector_t::const_iterator Partition::fixPointsBegin() const {
165  return fix.begin();
166 }
167 inline Partition::vector_t::const_iterator Partition::fixPointsEnd() const {
168  return fix.begin() + fixCounter;
169 }
170 inline unsigned long Partition::cellSize(unsigned int c) const {
171  return partitionCellLength[c];
172 }
173 
174 template<class ForwardIterator>
175 inline 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 
185 template<class ForwardIterator>
186 inline 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_
Partition(unsigned long n)
constructs an empty partition of length n
Definition: partition.h:142
vector_t::const_iterator fixPointsEnd() const
iterator to the end of fix points
Definition: partition.h:167
partition
Definition: partition.h:48
unsigned long cells() const
number of cells in this partition
Definition: partition.h:157
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
unsigned int fixPointsSize() const
number of fix points in this partition
Definition: partition.h:161
bool intersects(ForwardIterator begin, ForwardIterator end, unsigned int j) const
Definition: partition.h:175
backtrack refinement
Definition: backtrack_refinement.h:45
bool undoIntersection()
reverts the last intersection if there is one
Definition: partition.h:277
vector_t::const_iterator fixPointsBegin() const
iterator to the begin of fix points
Definition: partition.h:164
Definition: abstract_bsgs.h:49
unsigned long cellSize(unsigned int c) const
size of the c-th cell
Definition: partition.h:170