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            */
65            let max_pos = len - min_seg * (k - i);
66
67            if self.positions[i] < max_pos {
68                self.positions[i] += 1;
69                // Reset all positions after i
70                for j in (i + 1)..k {
71                    self.positions[j] = self.positions[j - 1] + min_seg;
72                }
73                return true;
74            }
75        }
76
77        self.done = true;
78        false
79    }
80}
81
82impl Iterator for CutCombinationIterator {
83    type Item = Vec<CutPoint>;
84
85    fn next(&mut self) -> Option<Self::Item> {
86        if self.done {
87            return None;
88        }
89
90        let cuts: Vec<CutPoint> = self
91            .positions
92            .iter()
93            .map(|&pos| CutPoint::new(self.entity_idx, pos))
94            .collect();
95
96        self.advance();
97
98        Some(cuts)
99    }
100}
101
102/// Counts the number of valid k-cut combinations for a route of length len.
103pub fn count_cut_combinations(k: usize, len: usize, min_seg: usize) -> usize {
104    // This is equivalent to C(n - (k+1)*min_seg + k, k)
105    // where we're choosing k positions from the "free" slots
106    let min_len = (k + 1) * min_seg;
107    if len < min_len {
108        return 0;
109    }
110
111    let free_slots = len - min_len + k;
112    binomial(free_slots, k)
113}
114
115/// Compute binomial coefficient C(n, k).
116pub fn binomial(n: usize, k: usize) -> usize {
117    if k > n {
118        return 0;
119    }
120    if k == 0 || k == n {
121        return 1;
122    }
123
124    let k = k.min(n - k); // Use symmetry
125    let mut result = 1;
126    for i in 0..k {
127        result = result * (n - i) / (i + 1);
128    }
129    result
130}
solverforge_solver/heuristic/selector/k_opt/iterators.rs

solverforge_solver/heuristic/selector/k_opt/
iterators.rs
