solverforge_solver/heuristic/selector/k_opt/
iterators.rs

1//! Iterators for k-opt cut combinations.
2
3use crate::heuristic::r#move::CutPoint;
4
5/// Iterator over all valid k-cut combinations for a route of given length.
6pub struct CutCombinationIterator {
7    k: usize,
8    len: usize,
9    min_seg: usize,
10    entity_idx: usize,
11    /// Current cut positions.
12    positions: Vec<usize>,
13    /// Whether we've exhausted all combinations.
14    done: bool,
15}
16
17impl CutCombinationIterator {
18    pub fn new(k: usize, len: usize, min_seg: usize, entity_idx: usize) -> Self {
19        // Minimum length required: k cuts need k+1 segments of min_seg each
20        let min_len = (k + 1) * min_seg;
21
22        if len < min_len {
23            return Self {
24                k,
25                len,
26                min_seg,
27                entity_idx,
28                positions: vec![],
29                done: true,
30            };
31        }
32
33        // Initialize with first valid combination
34        // Cuts must be at positions that leave min_seg elements between them
35        let mut positions = Vec::with_capacity(k);
36        for i in 0..k {
37            positions.push(min_seg * (i + 1));
38        }
39
40        Self {
41            k,
42            len,
43            min_seg,
44            entity_idx,
45            positions,
46            done: false,
47        }
48    }
49
50    fn advance(&mut self) -> bool {
51        if self.done || self.positions.is_empty() {
52            return false;
53        }
54
55        // Find the rightmost position that can be incremented
56        let k = self.k;
57        let len = self.len;
58        let min_seg = self.min_seg;
59
60        for i in (0..k).rev() {
61            // Maximum position for cut i:
62            // Need to leave room for (k - i - 1) more cuts after this one,
63            // each separated by min_seg, plus min_seg at the end
64            let max_pos = len - min_seg * (k - i);
65
66            if self.positions[i] < max_pos {
67                self.positions[i] += 1;
68                // Reset all positions after i
69                for j in (i + 1)..k {
70                    self.positions[j] = self.positions[j - 1] + min_seg;
71                }
72                return true;
73            }
74        }
75
76        self.done = true;
77        false
78    }
79}
80
81impl Iterator for CutCombinationIterator {
82    type Item = Vec<CutPoint>;
83
84    fn next(&mut self) -> Option<Self::Item> {
85        if self.done {
86            return None;
87        }
88
89        let cuts: Vec<CutPoint> = self
90            .positions
91            .iter()
92            .map(|&pos| CutPoint::new(self.entity_idx, pos))
93            .collect();
94
95        self.advance();
96
97        Some(cuts)
98    }
99}
100
101/// Counts the number of valid k-cut combinations for a route of length len.
102pub fn count_cut_combinations(k: usize, len: usize, min_seg: usize) -> usize {
103    // This is equivalent to C(n - (k+1)*min_seg + k, k)
104    // where we're choosing k positions from the "free" slots
105    let min_len = (k + 1) * min_seg;
106    if len < min_len {
107        return 0;
108    }
109
110    let free_slots = len - min_len + k;
111    binomial(free_slots, k)
112}
113
114/// Compute binomial coefficient C(n, k).
115pub fn binomial(n: usize, k: usize) -> usize {
116    if k > n {
117        return 0;
118    }
119    if k == 0 || k == n {
120        return 1;
121    }
122
123    let k = k.min(n - k); // Use symmetry
124    let mut result = 1;
125    for i in 0..k {
126        result = result * (n - i) / (i + 1);
127    }
128    result
129}
solverforge_solver/heuristic/selector/k_opt/iterators.rs

solverforge_solver/heuristic/selector/k_opt/
iterators.rs
