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_SET_PARTITION_ITERATOR_H_
#define PERMUTAHEDRAL_REPRESENTATION_SET_PARTITION_ITERATOR_H_
#include <vector>
#include <limits>
#include <boost/range/iterator_range.hpp>
namespace Gudhi {
namespace coxeter_triangulation {
typedef unsigned uint;
/** \brief Class that allows the user to generate set partitions of a set {0,...,n-1} in k parts.
*
*/
class Set_partition_iterator : public boost::iterator_facade< Set_partition_iterator,
std::vector<std::vector<uint> > const,
boost::forward_traversal_tag> {
typedef std::vector<std::vector<uint> > value_t;
protected:
friend class boost::iterator_core_access;
bool equal(Set_partition_iterator const& other) const {
return (is_end_ && other.is_end_);
}
value_t const& dereference() const {
return value_;
}
void update_value() {
for (uint i = 0; i < k_; i++)
value_[i].clear();
for (uint i = 0; i < n_; i++)
value_[rgs_[i]].push_back(i);
}
void increment() {
if (k_ <= 1) {
is_end_ = true;
return;
}
uint i = n_ - 1;
while (rgs_[i] + 1 > max_[i] ||
rgs_[i] + 1 >= k_)
i--;
if (i == 0) {
is_end_ = true;
return;
}
rgs_[i]++;
uint mm = max_[i];
mm += (rgs_[i] >= mm);
max_[i+1] = mm;
while (++i < n_) {
rgs_[i] = 0;
max_[i+1] = mm;
}
uint p = k_;
if (mm < p)
do {
max_[i] = p;
--i;
--p;
rgs_[i] = p;
} while (max_[i] < p);
update_value();
}
public:
Set_partition_iterator(const uint& n, const uint& k)
:
value_(k),
rgs_(n, 0),
max_(n+1),
is_end_(n == 0),
n_(n),
k_(k)
{
max_[0] = std::numeric_limits<uint>::max();
for (uint i = 0; i <= n-k; ++i)
value_[0].push_back(i);
for (uint i = n-k+1, j = 1; i < n; ++i, ++j) {
rgs_[i] = j;
value_[j].push_back(i);
}
for (uint i = 1; i <= n; i++)
max_[i] = rgs_[i-1] + 1;
update_value();
}
// Used for creating an end iterator
Set_partition_iterator() : is_end_(true), n_(0), k_(0) {}
void reinitialize() {
if (n_ > 0)
is_end_ = false;
for (uint i = 0; i <= n_-k_; ++i)
rgs_[i] = 0;
for (uint i = n_-k_+1, j = 1; i < n_; ++i, ++j)
rgs_[i] = j;
for (uint i = 1; i <= n_; i++)
max_[i] = rgs_[i-1] + 1;
update_value();
}
protected:
value_t value_; // the dereference value
std::vector<uint> rgs_; // restricted growth string
std::vector<uint> max_; // max_[i] = max(rgs_[0],...,rgs[i-1]) + 1
bool is_end_; // is true when the current permutation is the final one
uint n_;
uint k_;
};
} // namespace coxeter_triangulation
} // namespace Gudhi
#endif
|
