problemreductions/models/misc/
subset_product.rs

1//! Subset Product problem implementation.
2//!
3//! Given a set of positive integers and a target value, the problem asks whether
4//! any subset's product equals exactly the target. A multiplicative analogue of
5//! Subset Sum; NP-complete (see e.g. Garey & Johnson, 1979).
6//!
7//! This implementation uses arbitrary-precision integers (`BigUint`) so
8//! reductions can construct large instances without fixed-width overflow.
9
10use crate::registry::{FieldInfo, ProblemSchemaEntry};
11use crate::traits::Problem;
12use num_bigint::{BigUint, ToBigUint};
13use num_traits::{One, Zero};
14use serde::{Deserialize, Serialize};
15
16inventory::submit! {
17    ProblemSchemaEntry {
18        name: "SubsetProduct",
19        display_name: "Subset Product",
20        aliases: &[],
21        dimensions: &[],
22        category: crate::registry::ProblemCategory::Misc,
23        module_path: module_path!(),
24        description: "Find a subset of positive integers whose product equals exactly a target value",
25        fields: &[
26            FieldInfo { name: "sizes", type_name: "Vec<BigUint>", description: "Positive integer sizes s(a) for each element" },
27            FieldInfo { name: "target", type_name: "BigUint", description: "Target product B" },
28        ],
29    }
30}
31
32/// The Subset Product problem.
33///
34/// Given a set of `n` positive integers and a target `B`, determine whether
35/// there exists a subset whose elements multiply to exactly `B`.
36///
37/// # Representation
38///
39/// Each element has a binary variable: `x_i = 1` if element `i` is selected,
40/// `0` otherwise. The problem is satisfiable iff `∏_{i: x_i=1} sizes[i] == target`.
41///
42/// # Example
43///
44/// ```
45/// use problemreductions::models::misc::SubsetProduct;
46/// use problemreductions::{Problem, BruteForce};
47///
48/// let problem = SubsetProduct::new(vec![2u32, 3, 5, 7, 6, 10], 210u32);
49/// let solver = BruteForce::new();
50/// let solution = solver.solve(&problem).unwrap();
51/// assert!(solution.is_some());
52/// ```
53#[derive(Debug, Clone, Serialize, Deserialize)]
54pub struct SubsetProduct {
55    #[serde(with = "super::biguint_serde::decimal_biguint_vec")]
56    sizes: Vec<BigUint>,
57    #[serde(with = "super::biguint_serde::decimal_biguint")]
58    target: BigUint,
59}
60
61impl SubsetProduct {
62    /// Create a new SubsetProduct instance.
63    ///
64    /// # Panics
65    ///
66    /// Panics if any size is not positive (must be > 0) or if target is zero.
67    pub fn new<S, T>(sizes: Vec<S>, target: T) -> Self
68    where
69        S: ToBigUint,
70        T: ToBigUint,
71    {
72        let sizes: Vec<BigUint> = sizes
73            .into_iter()
74            .map(|s| s.to_biguint().expect("All sizes must be positive (> 0)"))
75            .collect();
76        assert!(
77            sizes.iter().all(|s| !s.is_zero()),
78            "All sizes must be positive (> 0)"
79        );
80        let target = target
81            .to_biguint()
82            .expect("SubsetProduct target must be nonnegative");
83        assert!(!target.is_zero(), "SubsetProduct target must be positive");
84        Self { sizes, target }
85    }
86
87    /// Create a SubsetProduct without validating sizes (for testing edge cases).
88    #[cfg(test)]
89    pub(crate) fn new_unchecked(sizes: Vec<BigUint>, target: BigUint) -> Self {
90        Self { sizes, target }
91    }
92
93    /// Returns the element sizes.
94    pub fn sizes(&self) -> &[BigUint] {
95        &self.sizes
96    }
97
98    /// Returns the target product.
99    pub fn target(&self) -> &BigUint {
100        &self.target
101    }
102
103    /// Returns the number of elements.
104    pub fn num_elements(&self) -> usize {
105        self.sizes.len()
106    }
107}
108
109impl Problem for SubsetProduct {
110    const NAME: &'static str = "SubsetProduct";
111    type Solution = Vec<bool>;
112    type Value = crate::types::Or;
113
114    crate::problem_parameters![("num_elements", num_elements),];
115
116    fn variant() -> Vec<(&'static str, &'static str)> {
117        crate::variant_params![]
118    }
119
120    fn evaluate(
121        &self,
122        config: &Self::Solution,
123    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
124        Ok({
125            crate::types::Or({
126                if config.len() != self.num_elements() {
127                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
128                        "subset-selection length does not match the elements".into(),
129                    ));
130                }
131                let mut product = BigUint::one();
132                for (i, &x) in config.iter().enumerate() {
133                    if x {
134                        product *= &self.sizes[i];
135                        if product > self.target {
136                            return Ok(crate::types::Or(false));
137                        }
138                    }
139                }
140                product == self.target
141            })
142        })
143    }
144}
145
146impl crate::solvers::BruteForceProblem for SubsetProduct {
147    fn dimensions(&self) -> Vec<usize> {
148        vec![2; self.num_elements()]
149    }
150}
151
152crate::declare_variants! {
153    default SubsetProduct => "2^num_elements",
154}
155
156crate::register_brute_force! {
157    SubsetProduct decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
158}
159
160#[cfg(feature = "example-db")]
161pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
162    // 6 elements [2,3,5,7,6,10], target 210 → select {2,3,5,7}
163    vec![crate::example_db::specs::ModelExampleSpec {
164        id: "subset_product",
165        instance: Box::new(SubsetProduct::new(vec![2u32, 3, 5, 7, 6, 10], 210u32)),
166        optimal_config: serde_json::json!(vec![true, true, true, true, false, false]),
167        optimal_value: serde_json::json!(true),
168    }]
169}
170
171#[cfg(test)]
172#[path = "../../unit_tests/models/misc/subset_product.rs"]
173mod tests;
problemreductions/models/misc/subset_product.rs

problemreductions/models/misc/
subset_product.rs
