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::{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        module_path: module_path!(),
18        description: "Determine whether a multiset of positive integers can be partitioned into two subsets of equal sum",
19        fields: &[
20            FieldInfo { name: "sizes", type_name: "Vec<u64>", description: "Positive integer size for each element" },
21        ],
22    }
23}
24
25/// The Partition problem.
26///
27/// Given a finite set `A` with `n` positive integer sizes, determine whether
28/// there exists a subset `A' ⊆ A` such that `∑_{a ∈ A'} s(a) = ∑_{a ∈ A\A'} s(a)`.
29///
30/// # Representation
31///
32/// Each element has a binary variable: `x_i = 1` if element `i` is in the
33/// second subset, `0` if in the first. The problem is satisfiable iff
34/// `∑_{i: x_i=1} sizes[i] = total_sum / 2`.
35///
36/// # Example
37///
38/// ```
39/// use problemreductions::models::misc::Partition;
40/// use problemreductions::{Problem, Solver, BruteForce};
41///
42/// let problem = Partition::new(vec![3, 1, 1, 2, 2, 1]);
43/// let solver = BruteForce::new();
44/// let solution = solver.find_witness(&problem);
45/// assert!(solution.is_some());
46/// ```
47#[derive(Debug, Clone, Serialize, Deserialize)]
48pub struct Partition {
49    sizes: Vec<u64>,
50}
51
52impl Partition {
53    /// Create a new Partition instance.
54    ///
55    /// # Panics
56    ///
57    /// Panics if `sizes` is empty or any size is zero.
58    pub fn new(sizes: Vec<u64>) -> Self {
59        assert!(!sizes.is_empty(), "Partition requires at least one element");
60        assert!(
61            sizes.iter().all(|&s| s > 0),
62            "All sizes must be positive (> 0)"
63        );
64        Self { sizes }
65    }
66
67    /// Returns the element sizes.
68    pub fn sizes(&self) -> &[u64] {
69        &self.sizes
70    }
71
72    /// Returns the number of elements.
73    pub fn num_elements(&self) -> usize {
74        self.sizes.len()
75    }
76
77    /// Returns the total sum of all sizes.
78    pub fn total_sum(&self) -> u64 {
79        self.sizes.iter().sum()
80    }
81}
82
83impl Problem for Partition {
84    const NAME: &'static str = "Partition";
85    type Value = crate::types::Or;
86
87    fn variant() -> Vec<(&'static str, &'static str)> {
88        crate::variant_params![]
89    }
90
91    fn dims(&self) -> Vec<usize> {
92        vec![2; self.num_elements()]
93    }
94
95    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
96        crate::types::Or({
97            if config.len() != self.num_elements() {
98                return crate::types::Or(false);
99            }
100            if config.iter().any(|&v| v >= 2) {
101                return crate::types::Or(false);
102            }
103            let selected_sum: u64 = config
104                .iter()
105                .enumerate()
106                .filter(|(_, &x)| x == 1)
107                .map(|(i, _)| self.sizes[i])
108                .sum();
109            selected_sum * 2 == self.total_sum()
110        })
111    }
112}
113
114crate::declare_variants! {
115    default Partition => "2^(num_elements / 2)",
116}
117
118#[cfg(feature = "example-db")]
119pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
120    vec![crate::example_db::specs::ModelExampleSpec {
121        id: "partition",
122        instance: Box::new(Partition::new(vec![3, 1, 1, 2, 2, 1])),
123        optimal_config: vec![1, 0, 0, 1, 0, 0],
124        optimal_value: serde_json::json!(true),
125    }]
126}
127
128#[cfg(test)]
129#[path = "../../unit_tests/models/misc/partition.rs"]
130mod tests;
problemreductions/models/misc/partition.rs

problemreductions/models/misc/
partition.rs
