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        module_path: module_path!(),
23        description: "Find a subset of positive integers whose product equals exactly a target value",
24        fields: &[
25            FieldInfo { name: "sizes", type_name: "Vec<BigUint>", description: "Positive integer sizes s(a) for each element" },
26            FieldInfo { name: "target", type_name: "BigUint", description: "Target product B" },
27        ],
28    }
29}
30
31/// The Subset Product problem.
32///
33/// Given a set of `n` positive integers and a target `B`, determine whether
34/// there exists a subset whose elements multiply to exactly `B`.
35///
36/// # Representation
37///
38/// Each element has a binary variable: `x_i = 1` if element `i` is selected,
39/// `0` otherwise. The problem is satisfiable iff `∏_{i: x_i=1} sizes[i] == target`.
40///
41/// # Example
42///
43/// ```
44/// use problemreductions::models::misc::SubsetProduct;
45/// use problemreductions::{Problem, Solver, BruteForce};
46///
47/// let problem = SubsetProduct::new(vec![2u32, 3, 5, 7, 6, 10], 210u32);
48/// let solver = BruteForce::new();
49/// let solution = solver.find_witness(&problem);
50/// assert!(solution.is_some());
51/// ```
52#[derive(Debug, Clone, Serialize, Deserialize)]
53pub struct SubsetProduct {
54    #[serde(with = "super::biguint_serde::decimal_biguint_vec")]
55    sizes: Vec<BigUint>,
56    #[serde(with = "super::biguint_serde::decimal_biguint")]
57    target: BigUint,
58}
59
60impl SubsetProduct {
61    /// Create a new SubsetProduct instance.
62    ///
63    /// # Panics
64    ///
65    /// Panics if any size is not positive (must be > 0) or if target is zero.
66    pub fn new<S, T>(sizes: Vec<S>, target: T) -> Self
67    where
68        S: ToBigUint,
69        T: ToBigUint,
70    {
71        let sizes: Vec<BigUint> = sizes
72            .into_iter()
73            .map(|s| s.to_biguint().expect("All sizes must be positive (> 0)"))
74            .collect();
75        assert!(
76            sizes.iter().all(|s| !s.is_zero()),
77            "All sizes must be positive (> 0)"
78        );
79        let target = target
80            .to_biguint()
81            .expect("SubsetProduct target must be nonnegative");
82        assert!(!target.is_zero(), "SubsetProduct target must be positive");
83        Self { sizes, target }
84    }
85
86    /// Create a SubsetProduct without validating sizes (for testing edge cases).
87    #[cfg(test)]
88    pub(crate) fn new_unchecked(sizes: Vec<BigUint>, target: BigUint) -> Self {
89        Self { sizes, target }
90    }
91
92    /// Returns the element sizes.
93    pub fn sizes(&self) -> &[BigUint] {
94        &self.sizes
95    }
96
97    /// Returns the target product.
98    pub fn target(&self) -> &BigUint {
99        &self.target
100    }
101
102    /// Returns the number of elements.
103    pub fn num_elements(&self) -> usize {
104        self.sizes.len()
105    }
106}
107
108impl Problem for SubsetProduct {
109    const NAME: &'static str = "SubsetProduct";
110    type Value = crate::types::Or;
111
112    fn variant() -> Vec<(&'static str, &'static str)> {
113        crate::variant_params![]
114    }
115
116    fn dims(&self) -> Vec<usize> {
117        vec![2; self.num_elements()]
118    }
119
120    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
121        crate::types::Or({
122            if config.len() != self.num_elements() {
123                return crate::types::Or(false);
124            }
125            if config.iter().any(|&v| v >= 2) {
126                return crate::types::Or(false);
127            }
128            let mut product = BigUint::one();
129            for (i, &x) in config.iter().enumerate() {
130                if x == 1 {
131                    product *= &self.sizes[i];
132                    if product > self.target {
133                        return crate::types::Or(false);
134                    }
135                }
136            }
137            product == self.target
138        })
139    }
140}
141
142crate::declare_variants! {
143    default SubsetProduct => "2^num_elements",
144}
145
146#[cfg(feature = "example-db")]
147pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
148    // 6 elements [2,3,5,7,6,10], target 210 → select {2,3,5,7}
149    vec![crate::example_db::specs::ModelExampleSpec {
150        id: "subset_product",
151        instance: Box::new(SubsetProduct::new(vec![2u32, 3, 5, 7, 6, 10], 210u32)),
152        optimal_config: vec![1, 1, 1, 1, 0, 0],
153        optimal_value: serde_json::json!(true),
154    }]
155}
156
157#[cfg(test)]
158#[path = "../../unit_tests/models/misc/subset_product.rs"]
159mod tests;
problemreductions/models/misc/subset_product.rs

problemreductions/models/misc/
subset_product.rs
