List the combinations that add up to 0 from a vector of numbers

Question

I'm writing a function that, given a Vec<i32> of numbers, lists the combinations that add up to 0. The code works, but it feels amateurish.

Specifically, the inside of the loop looks really ugly -- there must be a simpler way of doing this that avoids unwrap() and the repetition. Maybe with match?

fn calc_zer(input: Vec<i32>) -> Vec<(i32, i32, i32)> {
    let mut output: Vec<(i32, i32, i32)> = Vec::new();
    for a in (0..input.len() - 2) {
        for b in (a+1..input.len() -1) {
            for c in (b+1..input.len()) {
                if (input.get(a).unwrap() + input.get(b).unwrap() + input.get(c).unwrap() == 0) {
                    output.push((*input.get(a).unwrap(), *input.get(b).unwrap(), *input.get(c).unwrap()));
                }
            }
        }
    }
    output
}

Answer 1

1. Rust is a statically-compiled language, which means you get warnings and errors at compile time. Don't ignore those:

   warning: unnecessary parentheses around `for` head expression
    --> src/main.rs:3:14
     |
   3 |     for a in (0..input.len() - 2) {
     |              ^^^^^^^^^^^^^^^^^^^^
     |
     = note: #[warn(unused_parens)] on by default
   
   warning: unnecessary parentheses around `for` head expression
    --> src/main.rs:4:18
     |
   4 |         for b in (a+1..input.len() -1) {
     |                  ^^^^^^^^^^^^^^^^^^^^^
     |
     = note: #[warn(unused_parens)] on by default
   
   warning: unnecessary parentheses around `for` head expression
    --> src/main.rs:5:22
     |
   5 |             for c in (b+1..input.len()) {
     |                      ^^^^^^^^^^^^^^^^^^
     |
     = note: #[warn(unused_parens)] on by default
   
   warning: unnecessary parentheses around `if` condition
    --> src/main.rs:6:20
     |
   6 |                 if (input.get(a).unwrap() + input.get(b).unwrap() + input.get(c).unwrap() == 0) {
     |                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
     |
     = note: #[warn(unused_parens)] on by default
   

2. Next, run Clippy to get even more automated suggestions. Note that this contains the answer to your question:

   warning: this argument is passed by value, but not consumed in the function body
    --> src/main.rs:1:24
     |
   1 | pub fn calc_zer(input: Vec<i32>) -> Vec<(i32, i32, i32)> {
     |                        ^^^^^^^^ help: consider changing the type to `&[i32]`
     |
     = note: #[warn(needless_pass_by_value)] on by default
     = help: for further information visit https://github.com/Manishearth/rust-clippy/wiki#needless_pass_by_value
   
   warning: called `.get().unwrap()` on a Vec. Using `[]` is more clear and more concise
    --> src/main.rs:6:20
     |
   6 |                 if input.get(a).unwrap() + input.get(b).unwrap() + input.get(c).unwrap() == 0 {
     |                    ^^^^^^^^^^^^^^^^^^^^^ help: try this `&input[a]`
     |
     = note: #[warn(get_unwrap)] on by default
     = help: for further information visit https://github.com/Manishearth/rust-clippy/wiki#get_unwrap
   

3. Extract local variables so you don't even have the overhead of accessing the array multiple times.

4. There's no reason to provide an explicit type for output - it will be inferred from the return value.

5. Extract a variable for input.len() since that never changes during the iteration.

6. It's almost always better to iterate over the collection directly instead of indexing it. We can also use Iterator::enumerate to get the index as we go along.

This yields

fn calc_zer(input: &[i32]) -> Vec<(i32, i32, i32)> {
    let mut output = Vec::new();

    let len = input.len();

    for (a_i, &a) in input[0..len - 2].iter().enumerate() {
        for (b_i, &b) in input[a_i + 1..len - 1].iter().enumerate() {
            for &c in &input[a_i + b_i + 2..len] {
                if a + b + c == 0 {
                    output.push((a, b, c));
                }
            }
        }
    }

    output
}

This is a bit ugly, and even worse — I got it wrong originally! See the revision history for details. This was caused because enumerate starts counting from zero, even though we are iterating through an offset into the original vector.

However, Rust has a strong emphasis on reusing code via crates. In this example, I turn to one of my favorites — itertools:

extern crate itertools;

use itertools::Itertools;

fn calc_zer(input: &[i32]) -> Vec<(i32, i32, i32)> {
    input.iter()
        .tuple_combinations()
        .filter(|&(a, b, c)| a + b + c == 0)
        .map(|(&a, &b, &c)| (a, b, c))
        .collect()
}

Much more readable!

Answer 2

Let's do some complexity analysis! Your algorithm searches all combinations \${n \choose 3}\$ which is cubic time. We can improve this by sorting and being smarter about which triplets we visit.

For instance, say we have the the vector [-2, -1, 0, 1, 2]. We start by looking at (-2, -1, 2), whose sum is less than zero. Thus, we can rule out all (-2, -1, x) triplets since all remaining x are less than 2.

fn calc_zer(input_slice: &[i32]) -> Vec<(i32, i32, i32)> {
    let mut input = input_slice.to_vec();
    input.sort();
    let mut output = Vec::new();

    for i in 0..input.len() - 1 {
        let mut l = i + 1;
        let mut r = input.len() - 1;

        while l < r {
            let sum = input[i] + input[l] + input[r];

            if sum == 0 {
                output.push((input[i], input[l], input[r]));
                l += 1;
                r -= 1;
            } else if sum < 0 {
                l += 1;
            } else {
                r -= 1;
            }
        }
    }

    output
}

Here is the code, adapted from the GeeksForGeeks article linked below. It goes through each element, matches it with a (smallest, largest) pair and adjusts the pair if the sum is negative or positive.

This algorithm spends \$O(n \lg n)\$ time sorting and \$O(n)\$ time per element (the while loop), which yields a quadratic time complexity.

I compared the two algorithms by running them on a 1000 element input. The cubic algorithm took 4 minutes. The quadratic half a second.

Resources:

• Find all triplets with zero sum
• 3SUM
• Similar StackOverflow question

Answer 3

Shepmaster's solution with Itertools is fine (I assume it works) and may be the best way to go, in an absolute sense, but I don't believe it's the answer you were looking for. If you're still learning Rust you probably aren't familiar enough with the standard libraries to even know about tuple_combinations(). I think you wanted to fix your implementation rather than replace it with another. The fact that the other may somehow be better doesn't seem to be the point here.

Your gut told you, "the inside of the loop looks really ugly -- there must be a simpler way of doing this that avoids unwrap() and the repetition", so that's what I'll address.

uglyness: You have a lot of code that doesn't need to be there. Most of it is the unwrap() calls. Eliminating them will improve things. You don't need to declare a type for output since it's the return type—that may not always be true but it is here.

unwrap(): Why use get()? You have a vector (better yet, a slice) which supports indexing via [ ] notation. Boom—no more unwrap().

This is what I belive your solution should be:

pub fn calc_zer(input: &[i32]) -> Vec<(i32, i32, i32)> {
    let mut output = Vec::new();
    let end = input.len();
    for a in 0..end-2 {
        for b in a+1..end-1 {
            for c in b+1..end {
                let x = (input[a], input[c], input[c]);
                if x.0 + x.1 + x.2 == 0 { output.push(x); }
            }
        }
    }
    output
}

The only improvement I can claim is subjective; clarity. It's visually neat and tidy. There is less code to read, less to understand. That makes it easier to edit. That could support a claim of less error prone, but it's arguable.