problemreductions/rules/
partition_cosineproductintegration.rs

1//! Reduction from Partition to CosineProductIntegration.
2//!
3//! Given a Partition instance with sizes `[s_1, ..., s_n]`, construct a
4//! CosineProductIntegration instance with coefficients `[s_1, ..., s_n]`
5//! (cast from `u64` to `i64`).
6//!
7//! A balanced partition exists iff a balanced sign assignment exists:
8//! subset A has sum = total/2 iff the sign vector `ε_i = +1` for `i ∈ A`,
9//! `ε_i = -1` for `i ∉ A` satisfies `∑ ε_i s_i = 0`.
10//!
11//! Solution extraction is the identity mapping.
12
13use crate::models::misc::{CosineProductIntegration, Partition};
14use crate::reduction;
15use crate::rules::traits::{ReduceTo, ReductionResult};
16
17/// Result of reducing Partition to CosineProductIntegration.
18#[derive(Debug, Clone)]
19pub struct ReductionPartitionToCPI {
20    target: CosineProductIntegration,
21}
22
23impl ReductionResult for ReductionPartitionToCPI {
24    type Source = Partition;
25    type Target = CosineProductIntegration;
26
27    fn target_problem(&self) -> &Self::Target {
28        &self.target
29    }
30
31    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
32        target_solution.to_vec()
33    }
34}
35
36#[reduction(overhead = {
37    num_coefficients = "num_elements",
38})]
39impl ReduceTo<CosineProductIntegration> for Partition {
40    type Result = ReductionPartitionToCPI;
41
42    fn reduce_to(&self) -> Self::Result {
43        let coefficients: Vec<i64> = self.sizes().iter().map(|&s| s as i64).collect();
44        ReductionPartitionToCPI {
45            target: CosineProductIntegration::new(coefficients),
46        }
47    }
48}
49
50#[cfg(feature = "example-db")]
51pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
52    use crate::export::SolutionPair;
53
54    vec![crate::example_db::specs::RuleExampleSpec {
55        id: "partition_to_cosineproductintegration",
56        build: || {
57            // sizes [3, 1, 1, 2, 2, 1]: partition {3,2,1}={6} and {1,2,1}={4}? No...
58            // Actually [3,1,1,2,2,1] sum=10, need sum=5 each.
59            // config [1,0,0,1,0,0] → selected={3,2}=5, rest={1,1,2,1}=5 ✓
60            // sign assignment: bit=1→−, bit=0→+ : (+3,−1,−1,+2,−2,−1) = 3-1-1+2-2-1=0? No, 3-1-1+2-2-1=0. Yes!
61            // Wait: config [1,0,0,1,0,0] means elements 0,3 in subset 1.
62            // For CPI: bit 1 means −a_i. So −3+1+1−2+2+1 = 0. Yes!
63            crate::example_db::specs::rule_example_with_witness::<_, CosineProductIntegration>(
64                Partition::new(vec![3, 1, 1, 2, 2, 1]),
65                SolutionPair {
66                    source_config: vec![1, 0, 0, 1, 0, 0],
67                    target_config: vec![1, 0, 0, 1, 0, 0],
68                },
69            )
70        },
71    }]
72}
73
74#[cfg(test)]
75#[path = "../unit_tests/rules/partition_cosineproductintegration.rs"]
76mod tests;
problemreductions/rules/partition_cosineproductintegration.rs

problemreductions/rules/
partition_cosineproductintegration.rs
