problemreductions/models/misc/
kth_largest_m_tuple.rs

1//! Kth Largest m-Tuple problem implementation.
2//!
3//! Given m sets of positive integers and thresholds K and B, determine whether
4//! at least K distinct m-tuples (one element per set) have total size at least B.
5//! Garey & Johnson MP10.
6
7use crate::registry::{CreateSpec, ProblemSchemaEntry};
8use crate::traits::Problem;
9use crate::types::Or;
10use serde::de::Error as _;
11use serde::{Deserialize, Deserializer, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "KthLargestMTuple",
16        display_name: "Kth Largest m-Tuple",
17        aliases: &[],
18        dimensions: &[],
19        category: crate::registry::ProblemCategory::Misc,
20        module_path: module_path!(),
21        description: "Count m-tuples whose total size meets a bound and compare against a threshold K",
22        fields: KthLargestMTupleCreateSpec::FIELDS,
23    }
24}
25
26/// The Kth Largest m-Tuple problem.
27///
28/// Given sets `X_1, ..., X_m` of positive integers, a threshold `K`, and a
29/// bound `B`, determine whether at least `K` distinct m-tuples
30/// `(x_1, ..., x_m)` in `X_1 x ... x X_m` satisfy `sum(x_i) >= B`.
31///
32/// # Representation
33///
34/// The empty configuration triggers enumeration of the Cartesian product.
35/// `evaluate` returns `Or(true)` as soon as `K` qualifying tuples have been
36/// found and `Or(false)` if the complete product contains fewer than `K`.
37///
38/// # Example
39///
40/// ```
41/// use problemreductions::models::misc::KthLargestMTuple;
42/// use problemreductions::{Problem, BruteForce};
43///
44/// let problem = KthLargestMTuple::new(
45///     vec![vec![2, 5, 8], vec![3, 6], vec![1, 4, 7]],
46///     14,
47///     12,
48/// );
49/// let solver = BruteForce::new();
50/// let solution = solver.solve(&problem).unwrap().unwrap();
51/// // 14 of the 18 tuples have sum >= 12, so count >= K.
52/// assert_eq!(problem.evaluate(&solution).unwrap(), problemreductions::types::Or(true));
53/// ```
54#[derive(Debug, Clone, Serialize)]
55pub struct KthLargestMTuple {
56    sets: Vec<Vec<i64>>,
57    k: i64,
58    bound: i64,
59}
60
61#[derive(Debug, Deserialize, crate::CreateSpec)]
62struct KthLargestMTupleCreateSpec {
63    /// m sets, each containing positive integer sizes.
64    subsets: Vec<Vec<i64>>,
65    /// Threshold K (answer YES iff count >= K).
66    k: i64,
67    /// Lower bound B on tuple sum.
68    bound: i64,
69}
70
71impl TryFrom<KthLargestMTupleCreateSpec> for KthLargestMTuple {
72    type Error = crate::registry::ConstructionError;
73
74    fn try_from(spec: KthLargestMTupleCreateSpec) -> Result<Self, Self::Error> {
75        Self::try_new(spec.subsets, spec.k, spec.bound)
76    }
77}
78
79impl KthLargestMTuple {
80    fn validate(
81        sets: &[Vec<i64>],
82        k: i64,
83        bound: i64,
84    ) -> Result<(), crate::registry::ConstructionError> {
85        if sets.is_empty() {
86            return Err("KthLargestMTuple requires at least one set"
87                .to_string()
88                .into());
89        }
90        if sets.iter().any(|s| s.is_empty()) {
91            return Err("Every set must be non-empty".to_string().into());
92        }
93        sets.iter()
94            .try_fold(1usize, |total, set| total.checked_mul(set.len()))
95            .ok_or_else(|| {
96                crate::registry::ConstructionError::IntegerOverflow(
97                    "representing the total tuple count".into(),
98                )
99            })?;
100        if sets.iter().flatten().any(|&size| size <= 0) {
101            return Err("All sizes must be positive (> 0)".to_string().into());
102        }
103        if k <= 0 {
104            return Err("Threshold K must be positive".to_string().into());
105        }
106        if bound <= 0 {
107            return Err("Bound B must be positive".to_string().into());
108        }
109        Ok(())
110    }
111
112    /// Try to create a new KthLargestMTuple instance.
113    /// The total tuple count must fit in `usize`.
114    pub fn try_new(
115        sets: Vec<Vec<i64>>,
116        k: i64,
117        bound: i64,
118    ) -> Result<Self, crate::registry::ConstructionError> {
119        Self::validate(&sets, k, bound)?;
120        Ok(Self { sets, k, bound })
121    }
122
123    /// Create a new KthLargestMTuple instance.
124    ///
125    /// # Panics
126    ///
127    /// Panics if the inputs are invalid.
128    pub fn new(sets: Vec<Vec<i64>>, k: i64, bound: i64) -> Self {
129        Self::try_new(sets, k, bound).unwrap_or_else(|msg| panic!("{msg}"))
130    }
131
132    /// Returns the sets.
133    pub fn sets(&self) -> &[Vec<i64>] {
134        &self.sets
135    }
136
137    /// Returns the threshold K.
138    pub fn k(&self) -> i64 {
139        self.k
140    }
141
142    /// Returns the bound B.
143    pub fn bound(&self) -> i64 {
144        self.bound
145    }
146
147    /// Returns the number of sets (m).
148    pub fn num_sets(&self) -> usize {
149        self.sets.len()
150    }
151
152    /// Returns the total number of m-tuples (product of set sizes).
153    pub fn total_tuples(&self) -> usize {
154        self.sets.iter().map(Vec::len).product()
155    }
156
157    fn has_at_least_k_qualifying_tuples(&self) -> Result<bool, crate::traits::EvaluationError> {
158        let mut choices = vec![0; self.sets.len()];
159        let mut qualifying = 0;
160
161        loop {
162            let mut sum = 0i64;
163            for (set, &choice) in self.sets.iter().zip(&choices) {
164                sum = sum.checked_add(set[choice]).ok_or_else(|| {
165                    crate::traits::EvaluationError::IntegerOverflow(
166                        "summing a KthLargestMTuple tuple".to_string(),
167                    )
168                })?;
169            }
170            if sum >= self.bound {
171                qualifying += 1;
172                if qualifying == self.k {
173                    return Ok(true);
174                }
175            }
176
177            let mut advanced = false;
178            for set_index in (0..choices.len()).rev() {
179                choices[set_index] += 1;
180                if choices[set_index] == self.sets[set_index].len() {
181                    choices[set_index] = 0;
182                } else {
183                    advanced = true;
184                    break;
185                }
186            }
187            if !advanced {
188                return Ok(false);
189            }
190        }
191    }
192}
193
194#[derive(Deserialize)]
195struct KthLargestMTupleDef {
196    sets: Vec<Vec<i64>>,
197    k: i64,
198    bound: i64,
199}
200
201impl<'de> Deserialize<'de> for KthLargestMTuple {
202    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
203    where
204        D: Deserializer<'de>,
205    {
206        let data = KthLargestMTupleDef::deserialize(deserializer)?;
207        Self::try_new(data.sets, data.k, data.bound).map_err(D::Error::custom)
208    }
209}
210
211impl Problem for KthLargestMTuple {
212    const NAME: &'static str = "KthLargestMTuple";
213    type Solution = ();
214    type Value = Or;
215
216    crate::problem_parameters![("num_sets", num_sets), ("total_tuples", total_tuples),];
217
218    fn variant() -> Vec<(&'static str, &'static str)> {
219        crate::variant_params![]
220    }
221
222    fn evaluate(&self, _solution: &Self::Solution) -> Result<Or, crate::traits::EvaluationError> {
223        Ok(Or(self.has_at_least_k_qualifying_tuples()?))
224    }
225}
226
227impl crate::solvers::BruteForceProblem for KthLargestMTuple {
228    fn dimensions(&self) -> Vec<usize> {
229        vec![]
230    }
231}
232
233// Best known: brute-force enumeration of all tuples, O(total_tuples * num_sets).
234// No sub-exponential exact algorithm is known for the general case.
235crate::declare_variants! {
236    default KthLargestMTuple => "total_tuples * num_sets" create KthLargestMTupleCreateSpec,
237}
238
239crate::register_brute_force! {
240    KthLargestMTuple decode |_, _| (),
241}
242
243#[cfg(feature = "example-db")]
244pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
245    // m=3, X_1={2,5,8}, X_2={3,6}, X_3={1,4,7}, B=12, K=14.
246    // 14 of 18 tuples have sum >= 12, so the answer is YES at K=14.
247    vec![crate::example_db::specs::ModelExampleSpec {
248        id: "kth_largest_m_tuple",
249        instance: Box::new(KthLargestMTuple::new(
250            vec![vec![2, 5, 8], vec![3, 6], vec![1, 4, 7]],
251            14,
252            12,
253        )),
254        optimal_config: serde_json::json!(null),
255        optimal_value: serde_json::json!(true),
256    }]
257}
258
259#[cfg(test)]
260#[path = "../../unit_tests/models/misc/kth_largest_m_tuple.rs"]
261mod tests;
problemreductions/models/misc/kth_largest_m_tuple.rs

problemreductions/models/misc/
kth_largest_m_tuple.rs
