problemreductions/models/misc/
partition.rs

1//! Partition problem implementation.
2//!
3//! Given a finite set of positive integers, determine whether it can be
4//! partitioned into two subsets of equal sum. One of Karp's original 21
5//! NP-complete problems (1972), Garey & Johnson SP12.
6
7use crate::registry::{ConstructionError, FieldInfo, ProblemSchemaEntry};
8use crate::traits::Problem;
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "Partition",
14        display_name: "Partition",
15        aliases: &[],
16        dimensions: &[],
17        category: crate::registry::ProblemCategory::Misc,
18        module_path: module_path!(),
19        description: "Determine whether a multiset of positive integers can be partitioned into two subsets of equal sum",
20        fields: &[
21            FieldInfo { name: "sizes", type_name: "Vec<i64>", description: "Positive integer size for each element" },
22        ],
23    }
24}
25
26/// The Partition problem.
27///
28/// Given a finite set `A` with `n` positive integer sizes, determine whether
29/// there exists a subset `A' ⊆ A` such that `∑_{a ∈ A'} s(a) = ∑_{a ∈ A\A'} s(a)`.
30///
31/// # Representation
32///
33/// Each element has a binary variable: `x_i = 1` if element `i` is in the
34/// second subset, `0` if in the first. The problem is satisfiable iff
35/// `∑_{i: x_i=1} sizes[i] = total_sum / 2`.
36///
37/// # Example
38///
39/// ```
40/// use problemreductions::models::misc::Partition;
41/// use problemreductions::{Problem, BruteForce};
42///
43/// let problem = Partition::new(vec![3, 1, 1, 2, 2, 1]).unwrap();
44/// let solver = BruteForce::new();
45/// let solution = solver.solve(&problem).unwrap();
46/// assert!(solution.is_some());
47/// ```
48#[derive(Debug, Clone, Serialize)]
49pub struct Partition {
50    sizes: Vec<i64>,
51}
52
53impl Partition {
54    /// Create a new Partition instance.
55    ///
56    pub fn new(sizes: Vec<i64>) -> Result<Self, ConstructionError> {
57        if sizes.is_empty() {
58            return Err(ConstructionError::Conversion(
59                "Partition requires at least one element".into(),
60            ));
61        }
62        if sizes.iter().any(|&size| size <= 0) {
63            return Err(ConstructionError::Conversion(
64                "all Partition sizes must be positive".into(),
65            ));
66        }
67        sizes
68            .iter()
69            .try_fold(0i64, |sum, &size| sum.checked_add(size))
70            .ok_or_else(|| ConstructionError::IntegerOverflow("summing Partition sizes".into()))?;
71        Ok(Self { sizes })
72    }
73
74    /// Returns the element sizes.
75    pub fn sizes(&self) -> &[i64] {
76        &self.sizes
77    }
78
79    /// Returns the number of elements.
80    pub fn num_elements(&self) -> usize {
81        self.sizes.len()
82    }
83
84    /// Smallest h >= 1 such that every input size is strictly below 2^h.
85    pub fn max_numeric_magnitude_bits(&self) -> u64 {
86        crate::types::max_numeric_magnitude_bits(self.sizes.iter().copied())
87    }
88
89    /// Returns the total sum of all sizes.
90    pub fn total_sum(&self) -> i64 {
91        self.sizes.iter().sum()
92    }
93}
94
95impl<'de> Deserialize<'de> for Partition {
96    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
97    where
98        D: serde::Deserializer<'de>,
99    {
100        #[derive(Deserialize)]
101        struct Raw {
102            sizes: Vec<i64>,
103        }
104
105        let raw = Raw::deserialize(deserializer)?;
106        Self::new(raw.sizes).map_err(serde::de::Error::custom)
107    }
108}
109
110impl Problem for Partition {
111    const NAME: &'static str = "Partition";
112    type Solution = Vec<bool>;
113    type Value = crate::types::Or;
114
115    crate::problem_parameters![
116        ("max_numeric_magnitude_bits", max_numeric_magnitude_bits),
117        ("num_elements", num_elements),
118        ("total_sum", total_sum),
119    ];
120
121    fn variant() -> Vec<(&'static str, &'static str)> {
122        crate::variant_params![]
123    }
124
125    fn evaluate(
126        &self,
127        config: &Self::Solution,
128    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
129        Ok({
130            crate::types::Or({
131                if config.len() != self.num_elements() {
132                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
133                        "partition selection length does not match the elements".into(),
134                    ));
135                }
136                let selected_sum: i64 = config
137                    .iter()
138                    .enumerate()
139                    .filter(|(_, &x)| x)
140                    .map(|(i, _)| self.sizes[i])
141                    .sum();
142                selected_sum == self.total_sum() - selected_sum
143            })
144        })
145    }
146}
147
148impl crate::solvers::BruteForceProblem for Partition {
149    fn dimensions(&self) -> Vec<usize> {
150        vec![2; self.num_elements()]
151    }
152}
153
154crate::declare_variants! {
155    default Partition => "2^(num_elements / 2)",
156}
157
158crate::register_brute_force! {
159    Partition decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
160}
161
162#[cfg(feature = "example-db")]
163pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
164    vec![crate::example_db::specs::ModelExampleSpec {
165        id: "partition",
166        instance: Box::new(Partition::new(vec![3, 1, 1, 2, 2, 1]).unwrap()),
167        optimal_config: serde_json::json!(vec![true, false, false, true, false, false]),
168        optimal_value: serde_json::json!(true),
169    }]
170}
171
172#[cfg(test)]
173#[path = "../../unit_tests/models/misc/partition.rs"]
174mod tests;
problemreductions/models/misc/partition.rs

problemreductions/models/misc/
partition.rs
