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/// Returns one cut combination in the same lexicographic order as
116/// [`CutCombinationIterator`] without advancing through the preceding
117/// combinations. This keeps shuffled and random K-opt traversal lazy.
118pub(crate) fn cut_combination_at(
119    k: usize,
120    len: usize,
121    min_seg: usize,
122    entity_idx: usize,
123    mut rank: usize,
124) -> Option<Vec<CutPoint>> {
125    if k == 0 || min_seg == 0 {
126        return None;
127    }
128    let choice_count = len.checked_sub((k + 1).checked_mul(min_seg)?)? + k;
129    if rank >= binomial(choice_count, k) {
130        return None;
131    }
132
133    let mut choices = Vec::with_capacity(k);
134    let mut start = 0;
135    for position in 0..k {
136        let remaining = k - position - 1;
137        let maximum = choice_count - (k - position);
138        let mut selected = None;
139        for candidate in start..=maximum {
140            let suffix_count = binomial(choice_count - candidate - 1, remaining);
141            if rank < suffix_count {
142                selected = Some(candidate);
143                break;
144            }
145            rank -= suffix_count;
146        }
147        let selected = selected?;
148        choices.push(selected);
149        start = selected + 1;
150    }
151
152    Some(
153        choices
154            .into_iter()
155            .enumerate()
156            .map(|(position, choice)| {
157                CutPoint::new(entity_idx, choice + min_seg + position * (min_seg - 1))
158            })
159            .collect(),
160    )
161}
162
163/// Compute binomial coefficient C(n, k).
164pub fn binomial(n: usize, k: usize) -> usize {
165    if k > n {
166        return 0;
167    }
168    if k == 0 || k == n {
169        return 1;
170    }
171
172    let k = k.min(n - k); // Use symmetry
173    let mut result = 1;
174    for i in 0..k {
175        result = result * (n - i) / (i + 1);
176    }
177    result
178}
solverforge_solver/heuristic/selector/k_opt/iterators.rs

solverforge_solver/heuristic/selector/k_opt/
iterators.rs
