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    /// Returns the total sum of all sizes.
85    pub fn total_sum(&self) -> i64 {
86        self.sizes.iter().sum()
87    }
88}
89
90impl<'de> Deserialize<'de> for Partition {
91    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
92    where
93        D: serde::Deserializer<'de>,
94    {
95        #[derive(Deserialize)]
96        struct Raw {
97            sizes: Vec<i64>,
98        }
99
100        let raw = Raw::deserialize(deserializer)?;
101        Self::new(raw.sizes).map_err(serde::de::Error::custom)
102    }
103}
104
105impl Problem for Partition {
106    const NAME: &'static str = "Partition";
107    type Solution = Vec<bool>;
108    type Value = crate::types::Or;
109
110    crate::problem_parameters![("num_elements", num_elements),];
111
112    fn variant() -> Vec<(&'static str, &'static str)> {
113        crate::variant_params![]
114    }
115
116    fn evaluate(
117        &self,
118        config: &Self::Solution,
119    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
120        Ok({
121            crate::types::Or({
122                if config.len() != self.num_elements() {
123                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
124                        "partition selection length does not match the elements".into(),
125                    ));
126                }
127                let selected_sum: i64 = config
128                    .iter()
129                    .enumerate()
130                    .filter(|(_, &x)| x)
131                    .map(|(i, _)| self.sizes[i])
132                    .sum();
133                selected_sum == self.total_sum() - selected_sum
134            })
135        })
136    }
137}
138
139impl crate::solvers::BruteForceProblem for Partition {
140    fn dimensions(&self) -> Vec<usize> {
141        vec![2; self.num_elements()]
142    }
143}
144
145crate::declare_variants! {
146    default Partition => "2^(num_elements / 2)",
147}
148
149crate::register_brute_force! {
150    Partition decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
151}
152
153#[cfg(feature = "example-db")]
154pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
155    vec![crate::example_db::specs::ModelExampleSpec {
156        id: "partition",
157        instance: Box::new(Partition::new(vec![3, 1, 1, 2, 2, 1]).unwrap()),
158        optimal_config: serde_json::json!(vec![true, false, false, true, false, false]),
159        optimal_value: serde_json::json!(true),
160    }]
161}
162
163#[cfg(test)]
164#[path = "../../unit_tests/models/misc/partition.rs"]
165mod tests;
problemreductions/models/misc/partition.rs

problemreductions/models/misc/
partition.rs
