diff options
Diffstat (limited to 'src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Set_partition_iterator.h')
-rw-r--r-- | src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Set_partition_iterator.h | 111 |
1 files changed, 111 insertions, 0 deletions
diff --git a/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Set_partition_iterator.h b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Set_partition_iterator.h new file mode 100644 index 00000000..94ac10c2 --- /dev/null +++ b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Set_partition_iterator.h @@ -0,0 +1,111 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * 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> { + using value_t = std::vector<std::vector<uint>>; + + private: + 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(); + } + + private: + 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 |