description: Coefficients for extended min-max inclusion-exclusion: (-1)^(s-k) C(s-1,k-1) for subset size s.¶
minmax_inclusion_exclusion.hpp¶
Coefficients for extended min-max inclusion-exclusion: (-1)^(s-k) C(s-1,k-1) for subset size s.
\[
\displaystyle (-1)^{s-k}\binom{s-1}{k-1}
\]
Implementation¶
#ifndef NOYA_MINMAX_INCLUSION_EXCLUSION_HPP
#define NOYA_MINMAX_INCLUSION_EXCLUSION_HPP 1
/// @complexity Time: O(n 2^n) coefficient construction/evaluation.
/// Space: O(2^n).
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <vector>
namespace noya {
/// @brief Coefficients for extended min-max inclusion-exclusion:
/// (-1)^(s-k) C(s-1,k-1) for subset size s.
inline std::vector<std::int64_t> minmax_inclusion_exclusion_coefficients(
int element_count, int k) {
assert(1 <= k && k <= element_count);
std::vector<std::int64_t> result(element_count + 1);
std::int64_t combination = 1;
for (int subset_size = k; subset_size <= element_count; subset_size++) {
if (subset_size > k) {
combination = combination * (subset_size - 1) / (subset_size - k);
}
result[subset_size] =
((subset_size - k) & 1) ? -combination : combination;
}
return result;
}
namespace minmax_inclusion_exclusion_internal {
template <class T>
T transform(const std::vector<T> &subset_extrema, int k) {
assert(subset_extrema.size() >= 2 &&
std::has_single_bit(subset_extrema.size()));
int element_count = std::countr_zero(subset_extrema.size());
auto coefficient =
minmax_inclusion_exclusion_coefficients(element_count, k);
T result{};
for (std::size_t mask = 1; mask < subset_extrema.size(); mask++) {
result += subset_extrema[mask] *
static_cast<T>(coefficient[std::popcount(mask)]);
}
return result;
}
} // namespace minmax_inclusion_exclusion_internal
/// @brief Recover the k-th largest of n elements from the minimum of every
/// nonempty subset; k is one-indexed.
template <class T>
T kth_largest_from_subset_minima(const std::vector<T> &subset_minima, int k) {
return minmax_inclusion_exclusion_internal::transform(subset_minima, k);
}
/// @brief Recover the k-th smallest of n elements from the maximum of every
/// nonempty subset; k is one-indexed.
template <class T>
T kth_smallest_from_subset_maxima(const std::vector<T> &subset_maxima, int k) {
return minmax_inclusion_exclusion_internal::transform(subset_maxima, k);
}
} // namespace noya
#endif // NOYA_MINMAX_INCLUSION_EXCLUSION_HPP
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <vector>
/// @complexity Time: O(n 2^n) coefficient construction/evaluation.
/// Space: O(2^n).
namespace noya {
/// @brief Coefficients for extended min-max inclusion-exclusion:
/// (-1)^(s-k) C(s-1,k-1) for subset size s.
inline std::vector<std::int64_t> minmax_inclusion_exclusion_coefficients(
int element_count, int k) {
assert(1 <= k && k <= element_count);
std::vector<std::int64_t> result(element_count + 1);
std::int64_t combination = 1;
for (int subset_size = k; subset_size <= element_count; subset_size++) {
if (subset_size > k) {
combination = combination * (subset_size - 1) / (subset_size - k);
}
result[subset_size] =
((subset_size - k) & 1) ? -combination : combination;
}
return result;
}
namespace minmax_inclusion_exclusion_internal {
template <class T>
T transform(const std::vector<T> &subset_extrema, int k) {
assert(subset_extrema.size() >= 2 &&
std::has_single_bit(subset_extrema.size()));
int element_count = std::countr_zero(subset_extrema.size());
auto coefficient =
minmax_inclusion_exclusion_coefficients(element_count, k);
T result{};
for (std::size_t mask = 1; mask < subset_extrema.size(); mask++) {
result += subset_extrema[mask] *
static_cast<T>(coefficient[std::popcount(mask)]);
}
return result;
}
} // namespace minmax_inclusion_exclusion_internal
/// @brief Recover the k-th largest of n elements from the minimum of every
/// nonempty subset; k is one-indexed.
template <class T>
T kth_largest_from_subset_minima(const std::vector<T> &subset_minima, int k) {
return minmax_inclusion_exclusion_internal::transform(subset_minima, k);
}
/// @brief Recover the k-th smallest of n elements from the maximum of every
/// nonempty subset; k is one-indexed.
template <class T>
T kth_smallest_from_subset_maxima(const std::vector<T> &subset_maxima, int k) {
return minmax_inclusion_exclusion_internal::transform(subset_maxima, k);
}
} // namespace noya