Summation over an element of a tuple in a vector of tuples


#1

Hello everybody,

I am fairly new to Rust - in fact started a few days ago. What I try to achieve is the following:

There is a sorted vector of tuples - for simplicity let’s say that the tuple is comprised of 2 integers. E.g:

let mut v = vec![(1, 1), (1, 1), (1, 3), (1, 4), (2, 2), (2, 4), (2, 6)];

Now my questions is how to end up with a vector (could be the same one) that contains also tuples but with unique first element and the second element in the tuple is the sum of all the second tuple elements of the first vector corresponding to the unique first element, i.e. I want to end up with:

[(1, 9), (2, 12)]

Thanks for taking the time to read my question.


#2

OK, could you show the code you have written so far? What kind of data structures do you want to use to solve this problem, and why?


#3

After trying this by myself for practicing with iterators I found itertools::group_by which does the job of splitting the iterator over your vec into smaller iterators, each having the same key (first value in your tuples).

The next step computes the sum for each sub-iterator.

extern crate itertools;
use itertools::Itertools;

fn main() {
    let v = vec![(1, 1), (1, 1), (1, 3), (1, 4), (2, 2), (2, 4), (2, 6)];

    let groups = v.iter().group_by(|x| x.0);
    let sums = groups.into_iter().map(|(key, items)| (key, items.map(|item| item.1).sum()));
    let result: Vec<(i32, i32)> = sums.collect();
    
    println!("{:?}", result);
}

Maybe this equivalent is slightly more readable:

extern crate itertools;
use itertools::Itertools;

fn main() {
    let v = vec![(1, 1), (1, 1), (1, 3), (1, 4), (2, 2), (2, 4), (2, 6)];

    let groups = v.iter().group_by(|&&(key, _)| key);
    let sums = groups.into_iter().map(|(key, items)| (key, items.map(|&(_, value)| value).sum()));
    let result: Vec<(i32, i32)> = sums.collect();
    
    println!("{:?}", result);
}

#4

Hey,

Thank you for the reply. This is exactly what I was looking for. Had some idea that I should use an iterator adaptor like map but did not know exactly how to do it. This seems really elegant.


#5

@fyl2xp1 , you seem to have missed the point of my answer to the OP :slight_smile:


#6

Itertools coalesce deals well with this too, since it’s sorted (like group by requires too)

extern crate itertools;
use itertools::{cloned, Itertools};
use std::iter::FromIterator;

fn main() {
    let v = vec![(1, 1), (1, 1), (1, 3), (1, 4), (2, 2), (2, 4), (2, 6)];
    let res = Vec::from_iter(cloned(&v).coalesce(|u, v| {
        if u.0 == v.0 {
            Ok((u.0, u.1 + v.1))
        } else {
            Err((u, v))
        }
    }));
    println!("{:?}", res);
}

#7

Here is a solution without external dependencies:

let v = vec![(1, 1), (1, 1), (1, 3), (1, 4), (2, 2), (2, 4), (2, 6)];
let mut result = vec![];
if v.len() > 0 {
    let mut item = v[0];
    for &t in v.iter().skip(1) {
        if t.0 == item.0 {
            item.1 += t.1;
        } else {
            result.push(item);
            item = t;
        }
    }
    result.push(item);
}
print!("{:?}", result);

#8

Yeah, sorry. I took this for a practice for myself and when I finally had that solution I couldn’t resist to publish it :slight_smile:


#9

That seems to be the perfect match for the given problem.

What’s the difference between my collect() and your Vec::from_iter()?


#10

No difference other than how it is called.