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(
32        &self,
33        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
34    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
35        crate::rules::traits::validate_target_witness(
36            self.target_problem(),
37            target_solution,
38            |value| value.0,
39            "target witness does not satisfy the target problem",
40        )?;
41
42        Ok(target_solution.to_vec())
43    }
44}
45
46#[crate::aggregate_reduction(identity)]
47impl crate::rules::AggregateReductionResult for ReductionPartitionToCPI {}
48
49#[reduction(
50    transform = exact {
51        num_coefficients = "num_elements",
52    })]
53impl ReduceTo<CosineProductIntegration> for Partition {
54    type Result = ReductionPartitionToCPI;
55
56    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
57        let coefficients = self.sizes().to_vec();
58        Ok(ReductionPartitionToCPI {
59            target: CosineProductIntegration::new(coefficients),
60        })
61    }
62}
63
64#[cfg(feature = "example-db")]
65pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
66    use crate::export::SolutionPair;
67
68    vec![crate::example_db::specs::RuleExampleSpec {
69        id: "partition_to_cosineproductintegration",
70        build: || {
71            // sizes [3, 1, 1, 2, 2, 1]: partition {3,2,1}={6} and {1,2,1}={4}? No...
72            // Actually [3,1,1,2,2,1] sum=10, need sum=5 each.
73            // config [1,0,0,1,0,0] → selected={3,2}=5, rest={1,1,2,1}=5 ✓
74            // 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!
75            // Wait: config [1,0,0,1,0,0] means elements 0,3 in subset 1.
76            // For CPI: bit 1 means −a_i. So −3+1+1−2+2+1 = 0. Yes!
77            crate::example_db::specs::rule_example_with_witness::<_, CosineProductIntegration>(
78                Partition::new(vec![3, 1, 1, 2, 2, 1]).unwrap(),
79                SolutionPair {
80                    source_config: serde_json::json!(vec![true, false, false, true, false, false]),
81                    target_config: serde_json::json!(vec![true, false, false, true, false, false]),
82                },
83            )
84        },
85    }]
86}
87
88#[cfg(test)]
89#[path = "../unit_tests/rules/partition_cosineproductintegration.rs"]
90mod tests;
problemreductions/rules/partition_cosineproductintegration.rs

problemreductions/rules/
partition_cosineproductintegration.rs
