Using slice.windows(2) including a final iteration of the last and first items

Question

I am implementing a function that takes a list of indices representing a solution to the traveling salesman problem, and calculate the total travel distance using a distance matrix.

I need to iterate over the list in windows of 2 and aggregate the distances, including a last iteration of traveling back from the last index in the list to the first one.

I'm trying to solve it in a functional-style way, my current solution is:

fn calculate_solution_distance(solution: Vec<usize>, distance_matrix: Vec<Vec<i32>>) -> i32 {
    [solution.as_slice(), &[solution[0]]]
        .concat()
        .windows(2)
        .map(|indices| get_distance(indices[0], indices[1], &distance_matrix))
        .sum()
}

fn get_distance(from: usize, to: usize, distance_matrix: &Vec<Vec<i32>>) -> i32 {
    distance_matrix[from][to]
}

This code works. however it seems rather inefficient, speficially creating a slice from the first index just so I can concat it with a slice of my list. Is there a more efficient way to iterate over the list in windows of 2 such that the last item in the list is also iterated over twice?

[Why is it discouraged to accept a reference &String, &Vec, or &Box as a function argument?](https://stackoverflow.com/questions/40006219/why-is-it-discouraged-to-accept-a-reference-string-vec-or-box-as-a-function) Your `calculate_solution_distance` doesn't need to take owned values either. — cafce25, Apr 16 '23 at 09:41
To prevent allocations, you should use a slice `&[Vec]` for the `distance_matrix` function argument in `get_distance()` instead of a `&Vec>`. — Kaplan, Apr 20 '23 at 08:33

score 2 · Answer 1 · answered Apr 16 '23 at 10:05

Easily, just add the last pair:

fn calculate_solution_distance(solution: Vec<usize>, distance_matrix: Vec<Vec<i32>>) -> i32 {
    solution
        .windows(2)
        .chain(std::iter::once(
            &[solution[solution.len() - 1], solution[0]][..],
        ))
        .map(|indices| get_distance(indices[0], indices[1], &distance_matrix))
        .sum()
}

score 0 · Answer 2 · answered Apr 16 '23 at 13:19

There is also Itertools::circular_tuple_windows it uses Rust's std-offered Cycle and Take internally.

use itertools::Itertools;

fn main() {
    let a = [0,1,2,3,4,5];
    for (lhs, rhs) in a.iter().circular_tuple_windows() {
        dbg!((lhs, rhs));
    }
}

Using slice.windows(2) including a final iteration of the last and first items

2 Answers2