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        if sets.iter().flatten().any(|&size| size <= 0) {
94            return Err("All sizes must be positive (> 0)".to_string().into());
95        }
96        if k <= 0 {
97            return Err("Threshold K must be positive".to_string().into());
98        }
99        if bound <= 0 {
100            return Err("Bound B must be positive".to_string().into());
101        }
102        Ok(())
103    }
104
105    /// Try to create a new KthLargestMTuple instance.
106    pub fn try_new(
107        sets: Vec<Vec<i64>>,
108        k: i64,
109        bound: i64,
110    ) -> Result<Self, crate::registry::ConstructionError> {
111        Self::validate(&sets, k, bound)?;
112        Ok(Self { sets, k, bound })
113    }
114
115    /// Create a new KthLargestMTuple instance.
116    ///
117    /// # Panics
118    ///
119    /// Panics if the inputs are invalid.
120    pub fn new(sets: Vec<Vec<i64>>, k: i64, bound: i64) -> Self {
121        Self::try_new(sets, k, bound).unwrap_or_else(|msg| panic!("{msg}"))
122    }
123
124    /// Returns the sets.
125    pub fn sets(&self) -> &[Vec<i64>] {
126        &self.sets
127    }
128
129    /// Returns the threshold K.
130    pub fn k(&self) -> i64 {
131        self.k
132    }
133
134    /// Returns the bound B.
135    pub fn bound(&self) -> i64 {
136        self.bound
137    }
138
139    /// Returns the number of sets (m).
140    pub fn num_sets(&self) -> usize {
141        self.sets.len()
142    }
143
144    /// Returns the total number of m-tuples (product of set sizes).
145    pub fn total_tuples(&self) -> usize {
146        self.sets
147            .iter()
148            .try_fold(1usize, |total, set| total.checked_mul(set.len()))
149            .expect("KthLargestMTuple total tuple count exceeds usize")
150    }
151
152    fn has_at_least_k_qualifying_tuples(&self) -> Result<bool, crate::traits::EvaluationError> {
153        let mut choices = vec![0; self.sets.len()];
154        let mut qualifying = 0;
155
156        loop {
157            let mut sum = 0i64;
158            for (set, &choice) in self.sets.iter().zip(&choices) {
159                sum = sum.checked_add(set[choice]).ok_or_else(|| {
160                    crate::traits::EvaluationError::IntegerOverflow(
161                        "summing a KthLargestMTuple tuple".to_string(),
162                    )
163                })?;
164            }
165            if sum >= self.bound {
166                qualifying += 1;
167                if qualifying == self.k {
168                    return Ok(true);
169                }
170            }
171
172            let mut advanced = false;
173            for set_index in (0..choices.len()).rev() {
174                choices[set_index] += 1;
175                if choices[set_index] == self.sets[set_index].len() {
176                    choices[set_index] = 0;
177                } else {
178                    advanced = true;
179                    break;
180                }
181            }
182            if !advanced {
183                return Ok(false);
184            }
185        }
186    }
187}
188
189#[derive(Deserialize)]
190struct KthLargestMTupleDef {
191    sets: Vec<Vec<i64>>,
192    k: i64,
193    bound: i64,
194}
195
196impl<'de> Deserialize<'de> for KthLargestMTuple {
197    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
198    where
199        D: Deserializer<'de>,
200    {
201        let data = KthLargestMTupleDef::deserialize(deserializer)?;
202        Self::try_new(data.sets, data.k, data.bound).map_err(D::Error::custom)
203    }
204}
205
206impl Problem for KthLargestMTuple {
207    const NAME: &'static str = "KthLargestMTuple";
208    type Solution = ();
209    type Value = Or;
210
211    crate::problem_parameters![("num_sets", num_sets), ("total_tuples", total_tuples),];
212
213    fn variant() -> Vec<(&'static str, &'static str)> {
214        crate::variant_params![]
215    }
216
217    fn evaluate(&self, _solution: &Self::Solution) -> Result<Or, crate::traits::EvaluationError> {
218        Ok(Or(self.has_at_least_k_qualifying_tuples()?))
219    }
220}
221
222impl crate::solvers::BruteForceProblem for KthLargestMTuple {
223    fn dimensions(&self) -> Vec<usize> {
224        vec![]
225    }
226}
227
228// Best known: brute-force enumeration of all tuples, O(total_tuples * num_sets).
229// No sub-exponential exact algorithm is known for the general case.
230crate::declare_variants! {
231    default KthLargestMTuple => "total_tuples * num_sets" create KthLargestMTupleCreateSpec,
232}
233
234crate::register_brute_force! {
235    KthLargestMTuple decode |_, _| (),
236}
237
238#[cfg(feature = "example-db")]
239pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
240    // m=3, X_1={2,5,8}, X_2={3,6}, X_3={1,4,7}, B=12, K=14.
241    // 14 of 18 tuples have sum >= 12, so the answer is YES at K=14.
242    vec![crate::example_db::specs::ModelExampleSpec {
243        id: "kth_largest_m_tuple",
244        instance: Box::new(KthLargestMTuple::new(
245            vec![vec![2, 5, 8], vec![3, 6], vec![1, 4, 7]],
246            14,
247            12,
248        )),
249        optimal_config: serde_json::json!(null),
250        optimal_value: serde_json::json!(true),
251    }]
252}
253
254#[cfg(test)]
255#[path = "../../unit_tests/models/misc/kth_largest_m_tuple.rs"]
256mod tests;
problemreductions/models/misc/kth_largest_m_tuple.rs

problemreductions/models/misc/
kth_largest_m_tuple.rs
