CMR  1.3.0
permutations.hpp
Go to the documentation of this file.
1 #pragma once
2 
3 #include <utility>
4 #include <iostream>
5 #include <vector>
6 #include <map>
7 #include <exception>
8 #include <cassert>
9 #include <boost/random/uniform_int.hpp>
10 
11 namespace tu
12 {
13 
18  class permutation_shrink_exception: std::exception
19  {
20  public:
22  {
23 
24  }
25 
26  virtual ~permutation_shrink_exception() throw ()
27  {
28 
29  }
30 
31  virtual const char* what() const throw ()
32  {
33  return "Cannot shrink permutation";
34  }
35  };
36 
44  {
45  public:
46  typedef size_t size_type;
47  typedef ptrdiff_t difference_type;
48  typedef size_t value_type;
49  typedef std::vector <value_type> data_type;
50 
51  protected:
52  data_type _data;
53 
54  public:
55 
63  permutation(size_type size = 0)
64  {
65  reset(size);
66  }
67 
76  template <typename RandomNumberGenerator>
77  permutation(size_type size, RandomNumberGenerator& rng)
78  {
79  reset(size);
80  shuffle(rng);
81  }
82 
89  permutation(const permutation& other)
90  {
91  _data.resize(other.size());
92  for (size_type i = 0; i < _data.size(); ++i)
93  _data[i] = other._data[i];
94  }
95 
100  virtual ~permutation()
101  {
102 
103  }
104 
111  void reset(size_t new_size)
112  {
113  _data.resize(new_size);
114  for (size_type i = 0; i < new_size; ++i)
115  {
116  _data[i] = i;
117  }
118  }
119 
124  inline void reset()
125  {
126  reset(_data.size());
127  }
128 
135  template <typename RandomNumberGenerator>
136  void shuffle(RandomNumberGenerator& rng)
137  {
138  for (size_t i = 0; i < _data.size(); ++i)
139  {
140  boost::uniform_int <int> dist(i, _data.size() - 1);
141  size_t j = dist(rng);
142  swap(i, j);
143  }
144  }
145 
150  inline size_type size() const
151  {
152  return _data.size();
153  }
154 
162  inline value_type operator()(value_type index) const
163  {
164  return get(index);
165  }
166 
173  inline value_type get(value_type index) const
174  {
175  assert (index < _data.size());
176 
177  return _data[index];
178  }
179 
187  inline void swap(value_type a, value_type b)
188  {
189  std::swap(_data[a], _data[b]);
190  }
191 
199  void rswap(value_type a, value_type b)
200  {
201  value_type tmp, pa = a, pb = b;
202  while ((tmp = get(pa)) != a)
203  pa = tmp;
204  while ((tmp = get(pb)) != b)
205  pb = tmp;
206  swap(pa, pb);
207  }
208 
213  void revert()
214  {
216  value_type* temp = new value_type[size()];
217  for (size_type i = 0; i < size(); ++i)
218  temp[i] = _data[i];
219 
220  for (size_type i = 0; i < size(); ++i)
221  _data[temp[i]] = i;
222  delete[] temp;
223  }
224 
230  {
231  permutation result(size());
232  for (size_type i = 0; i < size(); ++i)
233  result._data[get(i)] = i;
234  return result;
235  }
236 
245  {
246  _data.resize(other.size());
247  for (size_type i = 0; i < _data.size(); ++i)
248  _data[i] = other._data[i];
249  return *this;
250  }
251 
262  {
263  assert (size() == rhs.size());
264 
265  permutation result(size());
266  for (size_type i = 0; i < size(); ++i)
267  result._set(i, _data[rhs(i)]);
268 
269  return result;
270  }
271 
280  void resize(size_type new_size)
281  {
282  size_type old_size = size();
283  for (size_type i = new_size; i < old_size; ++i)
284  {
285  if (_data[i] < new_size)
287  }
288 
289  _data.resize(new_size);
290  for (size_type i = old_size; i < new_size; i++)
291  _data[i] = i;
292  }
293 
300  inline void grow(difference_type by)
301  {
302  resize(size() + by);
303  }
304 
311  inline void shrink(difference_type by)
312  {
313  resize(size() - by);
314  }
315 
316  protected:
317 
319 
321 
323 
324  template <class Less>
325  friend void sort(permutation& permutation, size_t first, size_t beyond, Less& less);
326 
334  void _set(value_type index, value_type value)
335  {
336  _data[index] = value;
337  }
338 
343  inline data_type& get_data()
344  {
345  return _data;
346  }
347 
348  };
349 
357  {
358  public:
359  typedef size_t size_type;
360  typedef std::vector <permutation::value_type> memberlist_type;
361  typedef std::pair <memberlist_type*, permutation*> groupinfo_type;
362  typedef std::map <int, groupinfo_type> state_type;
363 
364  private:
365  size_type _size;
366  state_type _state;
367  permutation _permutation;
368 
369  public:
370 
379  _permutation(size)
380  {
381  if (size)
382  {
383  memberlist_type* memberlist = new memberlist_type();
384  memberlist->resize(size);
385  for (permutation::size_type i = 0; i < size; i++)
386  (*memberlist)[i] = i;
387  permutation* perm = new permutation(size);
388  _state[0] = groupinfo_type(memberlist, perm);
389  }
390  }
391 
400  permutation_enumerator(const std::vector <permutation::value_type>& groups) :
401  _permutation(groups.size())
402  {
403  _size = groups.size();
404  for (size_t i = 0; i < groups.size(); ++i)
405  {
406  state_type::iterator iter = _state.find(groups[i]);
407  if (iter == _state.end())
408  {
409  _state[groups[i]] = groupinfo_type(new memberlist_type(), NULL);
410  _state[groups[i]].first->push_back(i);
411  }
412  else
413  {
414  iter->second.first->push_back(i);
415  }
416  }
417  for (state_type::iterator iter = _state.begin(); iter != _state.end(); ++iter)
418  {
419  groupinfo_type& info = iter->second;
420  info.second = new permutation(info.first->size());
421  }
422  }
423 
429  {
430  for (state_type::iterator iter = _state.begin(); iter != _state.end(); ++iter)
431  {
432  delete iter->second.first;
433  delete iter->second.second;
434  }
435  }
436 
441  inline bool empty()
442  {
443  return _size == 0;
444  }
445 
453  virtual bool enumerate()
454  {
455  if (empty())
456  return true;
457 
458  return enumerate_group(_state.begin(), 0);
459  }
460 
461  protected:
462 
471  virtual bool visitor(const permutation& perm) = 0;
472 
473  private:
474 
483  bool enumerate_group(state_type::iterator state, permutation::size_type index)
484  {
486  if (state == _state.end())
487  {
488  for (state = _state.begin(); state != _state.end(); ++state)
489  {
490  const memberlist_type& memberlist = *(state->second.first);
491  const permutation& perm = *(state->second.second);
492  for (permutation::size_type i = 0; i < perm.size(); i++)
493  {
494  _permutation._set(memberlist[i], memberlist[perm(i)]);
495  }
496  }
497 
498  return visitor(_permutation);
499  }
500 
502  if (index >= state->second.first->size())
503  {
504  return enumerate_group(++state, 0);
505  }
506 
508  permutation& p = *(state->second.second);
509  for (permutation::size_type i = 0; i < p.size(); i++)
510  {
511  bool found = false;
512  for (permutation::size_type j = 0; j < index; j++)
513  {
514  if (p(j) == i)
515  {
516  found = true;
517  break;
518  }
519  }
520  if (!found)
521  {
522  p._set(index, i);
523  if (!enumerate_group(state, index + 1))
524  return false;
525  }
526  }
527 
528  return true;
529  }
530  };
531 
540  inline bool operator==(const permutation& p, const permutation& q)
541  {
542  if (p.size() != q.size())
543  return false;
544 
545  for (size_t i = 0; i < p.size(); ++i)
546  {
547  if (p(i) != q(i))
548  return false;
549  }
550  return true;
551  }
552 
561  inline std::ostream& operator<<(std::ostream& stream, const permutation& p)
562  {
563  if (p.size() > 0)
564  {
565  stream << p(0);
566  for (size_t i = 1; i < p.size(); i++)
567  stream << ' ' << p(i);
568  }
569  return stream;
570  }
571 
582  template <class Less>
583  inline void sort(permutation& permutation, size_t first, size_t beyond, Less& less)
584  {
585  permutation::data_type& data = permutation.get_data();
586  std::sort(data.begin() + first, data.begin() + beyond, less);
587  }
588 
597  template <class Less>
598  inline void sort(permutation& permutation, Less& less)
599  {
600  sort(permutation, 0, permutation.size(), less);
601  }
602 
603 } /* namespace tu */
virtual ~permutation_shrink_exception()
Definition: permutations.hpp:26
void _set(value_type index, value_type value)
Definition: permutations.hpp:334
Definition: algorithm.hpp:13
size_t value_type
Definition: permutations.hpp:48
virtual ~permutation_enumerator()
Definition: permutations.hpp:428
permutation_enumerator(const std::vector< permutation::value_type > &groups)
Definition: permutations.hpp:400
size_t size_type
Definition: permutations.hpp:46
data_type & get_data()
Definition: permutations.hpp:343
permutation(size_type size=0)
Definition: permutations.hpp:63
permutation reverse() const
Definition: permutations.hpp:229
std::vector< permutation::value_type > memberlist_type
Definition: permutations.hpp:360
size_t size_type
Definition: permutations.hpp:359
void revert()
Definition: permutations.hpp:213
bool operator==(const permutation &p, const permutation &q)
Definition: permutations.hpp:540
virtual bool enumerate()
Definition: permutations.hpp:453
size_type size() const
Definition: permutations.hpp:150
bool empty()
Definition: permutations.hpp:441
permutation & operator=(const permutation &other)
Definition: permutations.hpp:244
void sort(permutation &permutation, size_t first, size_t beyond, Less &less)
Definition: permutations.hpp:583
permutation_enumerator(permutation::size_type size)
Definition: permutations.hpp:378
std::vector< value_type > data_type
Definition: permutations.hpp:49
permutation(size_type size, RandomNumberGenerator &rng)
Definition: permutations.hpp:77
void sort(permutation &permutation, Less &less)
Definition: permutations.hpp:598
std::ostream & operator<<(std::ostream &stream, const binary_linear_space &space)
Definition: binary_linear_space.hpp:205
ptrdiff_t difference_type
Definition: permutations.hpp:47
void rswap(value_type a, value_type b)
Definition: permutations.hpp:199
void swap(value_type a, value_type b)
Definition: permutations.hpp:187
permutation(const permutation &other)
Definition: permutations.hpp:89
permutation_shrink_exception()
Definition: permutations.hpp:21
virtual const char * what() const
Definition: permutations.hpp:31
data_type _data
Definition: permutations.hpp:52
permutation operator*(const permutation &rhs) const
Definition: permutations.hpp:261
Definition: permutations.hpp:18
void shuffle(RandomNumberGenerator &rng)
Definition: permutations.hpp:136
value_type operator()(value_type index) const
Definition: permutations.hpp:162
std::map< int, groupinfo_type > state_type
Definition: permutations.hpp:362
void grow(difference_type by)
Definition: permutations.hpp:300
Definition: permutations.hpp:356
std::pair< memberlist_type *, permutation * > groupinfo_type
Definition: permutations.hpp:361
void shrink(difference_type by)
Definition: permutations.hpp:311
Definition: permutations.hpp:43
void reset()
Definition: permutations.hpp:124
void resize(size_type new_size)
Definition: permutations.hpp:280
void reset(size_t new_size)
Definition: permutations.hpp:111
virtual ~permutation()
Definition: permutations.hpp:100