vrp_pragmatic/utils/
permutations.rs

1use rand::prelude::SliceRandom;
2use std::collections::HashSet;
3use std::sync::Arc;
4use vrp_core::models::problem::JobPermutation;
5use vrp_core::prelude::*;
6
7#[cfg(test)]
8#[path = "../../tests/unit/utils/permutations_test.rs"]
9mod permutations_test;
10
11pub struct VariableJobPermutation {
12    size: usize,
13    split_start_index: usize,
14    sample_size: usize,
15    random: Arc<dyn Random + Sync + Send>,
16}
17
18impl VariableJobPermutation {
19    pub fn new(
20        size: usize,
21        split_start_index: usize,
22        sample_size: usize,
23        random: Arc<dyn Random + Sync + Send>,
24    ) -> Self {
25        assert!(size > 0);
26        Self { size, split_start_index, sample_size, random }
27    }
28}
29
30impl JobPermutation for VariableJobPermutation {
31    fn get(&self) -> Vec<Vec<usize>> {
32        get_split_permutations(self.size, self.split_start_index, self.sample_size, self.random.as_ref())
33    }
34
35    fn validate(&self, permutation: &[usize]) -> bool {
36        permutation.iter().cloned().collect::<HashSet<_>>().len() == self.size
37            && permutation[0..self.split_start_index].iter().max().map_or(false, |&max| max < self.split_start_index)
38            && permutation[self.split_start_index..].iter().min().map_or(false, |&min| min >= self.split_start_index)
39    }
40}
41
42fn generate_sample_permutations(
43    start: usize,
44    end: usize,
45    sample_size: usize,
46    random: &(dyn Random + Sync + Send),
47) -> Vec<Vec<usize>> {
48    // NOTE prevent to have more then possible unique permutations for simple cases
49    let size = end - start + 1;
50    let sample_size = if size < 10 {
51        let total_permutations = (1..=size).product();
52        sample_size.min(total_permutations)
53    } else {
54        sample_size
55    };
56
57    let data = (start..=end).collect::<Vec<_>>();
58    let mut result = vec![data; sample_size];
59    let mut rng = random.get_rng();
60    result.iter_mut().for_each(|data| {
61        data.shuffle(&mut rng);
62    });
63
64    result
65}
66
67fn get_split_permutations(
68    size: usize,
69    split_start_index: usize,
70    sample_size: usize,
71    random: &(dyn Random + Sync + Send),
72) -> Vec<Vec<usize>> {
73    // TODO make it memory efficient somehow
74
75    match split_start_index {
76        x if x == 0 || x == size => generate_sample_permutations(0, size - 1, sample_size, random),
77        _ => {
78            assert!(size > split_start_index);
79
80            let first = generate_sample_permutations(0, split_start_index - 1, sample_size, random);
81            let second = generate_sample_permutations(split_start_index, size - 1, sample_size, random);
82
83            first
84                .iter()
85                .flat_map(|a| {
86                    second
87                        .iter()
88                        .map(|b| a.iter().chain(b.iter()).cloned().collect::<Vec<usize>>())
89                        .collect::<Vec<Vec<usize>>>()
90                })
91                .take(sample_size)
92                .collect()
93        }
94    }
95}
vrp_pragmatic/utils/permutations.rs

vrp_pragmatic/utils/
permutations.rs
