1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
/* This file is part of the Gudhi Library. The Gudhi library
* (Geometric Understanding in Higher Dimensions) is a generic C++
* library for computational topology.
*
* Author(s): Siargey Kachanovich
*
* Copyright (C) 2019 Inria
*
* Modification(s):
* - YYYY/MM Author: Description of the modification
*/
#ifndef PERMUTAHEDRAL_REPRESENTATION_PERMUTATION_ITERATOR_H_
#define PERMUTAHEDRAL_REPRESENTATION_PERMUTATION_ITERATOR_H_
#include <vector>
#include <boost/range/iterator_range.hpp>
namespace Gudhi {
namespace coxeter_triangulation {
typedef unsigned uint;
/** \brief Class that allows the user to generate permutations.
* Based on the optimization of the Heap's algorithm by Sedgewick.
*/
class Permutation_iterator : public boost::iterator_facade< Permutation_iterator,
std::vector<uint> const,
boost::forward_traversal_tag> {
typedef std::vector<uint> value_t;
protected:
friend class boost::iterator_core_access;
bool equal(Permutation_iterator const& other) const {
return (is_end_ && other.is_end_);
}
value_t const& dereference() const {
return value_;
}
void swap_two_indices(std::size_t i, std::size_t j) {
uint t = value_[i];
value_[i] = value_[j];
value_[j] = t;
}
void elementary_increment() {
uint j = 0;
while (d_[j] == j+1) {
d_[j] = 0;
++j;
}
if (j == n_ - 1) {
is_end_ = true;
return;
}
uint k = j+1;
uint x = (k%2 ? d_[j] : 0);
swap_two_indices(k, x);
++d_[j];
}
void elementary_increment_optim_3() {
if (ct_ != 0) {
--ct_;
swap_two_indices(1 + (ct_%2), 0);
}
else {
ct_ = 5;
uint j = 2;
while (d_[j] == j+1) {
d_[j] = 0;
++j;
}
if (j == n_ - 1) {
is_end_ = true;
return;
}
uint k = j+1;
uint x = (k%2 ? d_[j] : 0);
swap_two_indices(k, x);
++d_[j];
}
}
void increment() {
if (optim_3_)
elementary_increment_optim_3();
else
elementary_increment();
}
public:
Permutation_iterator(const uint& n)
:
value_(n),
is_end_(n == 0),
optim_3_(n >= 3),
n_(n),
d_(n),
ct_(5)
{
for (uint i = 0; i < n; ++i) {
value_[i] = i;
d_[i] = 0;
}
if (n > 0)
d_[n-1] = -1;
}
// Used for the creating an end iterator
Permutation_iterator() : is_end_(true), n_(0) {}
void reinitialize() {
if (n_ > 0)
is_end_ = false;
}
protected:
value_t value_; // the dereference value
bool is_end_; // is true when the current permutation is the final one
bool optim_3_; // true if n>=3. for n >= 3, the algorithm is optimized
uint n_;
std::vector<uint> d_; // mix radix digits with radix [2 3 4 ... n-1 (sentinel=-1)]
uint ct_; // counter with values in {0,...,5} used in the n>=3 optimization.
};
} // namespace coxeter_triangulation
} // namespace Gudhi
#endif
|
