Generate all non-redundant tuple combinations of indices

Struggling to formulate a sensible topic for this question... In short, I'd like to find a nicer way to generate 'idx' than using the following nested for loops:

 for i in 0..N {
        for j in i + 1..N {
             let idx = (i, j)
        }
    }

Any suggestions?

Itertools::tuple_combinations

6 Likes

Thanks @ExpHp. Any nice way to do it without external crates?

1 Like

Your way isn't bad to be honest; but if you really want something more ergonomic, your code can be factored out into a function:

fn pairs_smaller_than (
    n: usize,
) -> impl Iterator<Item = (usize, usize)> + 'static
{
    (0 .. n).flat_map(move |i| {
        (i + 1 .. n).map(move |j| (i, j))
    })
}

fn main ()
{
    for (i, j) in pairs_smaller_than(4) {
        println!("({}, {})", i, j);
    }
}

That being said, there is nothing wrong with depending on a crate, specially one as pervasive as ::itertools

4 Likes

Thanks @Yandros, that's pretty much what I was looking for, although I would probably also use itertools as suggested for non-learning purposes.

The only thing I don't quite understand in your example is why you have added the "+ 'static" annotation to the return value of pairs_smaller_than. Is the reason to enforce the returned iterator to have static lifetime?

A function returning -> impl ... is erasing the actual type returned and just giving a minimal amount of information about it: what traits it implements, and its lifetime.

That's why impl ... (as well as dyn ...) both carry a lifetime parameter: impl Trait + 'lifetime. It is very very often elided, and in that case it is usually 'static. Every once in a while this will be false and lead to errors. That's why I prefer to be very explicit about it, and not hide that in this case it is indeed 'static.

  • Having T : 'static means that a value of type T does not borrow from any local, which implies that the returned value can be held and used afterwards at any time, not matter how "late".

  • In this case, since there are no input arguments to the function, there is no other candidate for a lifetime. This is better seen with a counterexample:

    fn pairs_smaller_than (
        n: &'_ usize,
    ) -> impl Iterator<Item = (usize, usize)> + '_ // returned value cannot outlive input borrow
    {
        (0 .. *n).flat_map(move |i| {
            (i + 1 .. *n).map(move |j| (i, j))
        })
    }
    
    fn main ()
    {
        for (i, j) in {
                let four = 4;
                pairs_smaller_than(&four)
            }
        {
            println!("({}, {})", i, j);
        }
    }
    
1 Like

Thanks again for a great explanation, makes sense now.

I'm also wondering if there is any way to avoid having to use "move" lambdas? I understand that they are needed to avoid creating references to variables that may be outlived by the returned Iterator, but adding "move" to both lambdas seem a bit verbose and cluttered to me as a rust novice.

:+1:

Sadly there isn't. Rust is sometimes overly verbose, but that's the price to pay for such a precise level of control. The other way around would be even more verbose:

Hypothetical Rust where all closures would be move

Rust could have chosen to make all closures be move, but then non-move closures would become even more cumbersome to write (compared to just writing move for a move closure), and this in turn would make the language even harder for novices:

Example
  • Imagine having a non-Copy variable around, such as a String,
use ::std::{
    fs::File,
    io::Write,
};

fn foo (filename: String)
{
    let mut file =
        File::create(&filename)
            .unwrap_or_else(|err| panic!(
                "Failed to create {:?}: {}", &filename, err,
            ))
    ;
    let contents = "Hello, World!";
    file.write_all(contents.as_bytes())
        .unwrap_or_else(|err| panic!(
            "Failed to write {:?} into {:?}: {}",
            contents, &filename, err,
        ))
    ;
    filename
}

which would error with:

error[E0382]: use of moved value: `filename`
  --> src/lib.rs:16:25
   |
6  | fn foo (filename: String)
   |         -------- move occurs because `filename` has type `std::string::String`, which does not implement the `Copy` trait
...
10 |             .unwrap_or_else(|err| panic!(
   |                             ---------- value moved into closure here
11 |                 "Failed to create {:?}: {}", &filename, err,
   |                                              --------- variable moved due to use in closure
...
16 |         .unwrap_or_else(|err| panic!(
   |                         ^^^^^^^^^^ value used here after move
17 |             "Failed to write {:?} into {:?}: {}",
18 |             contents, &filename, err,
   |                       --------- use occurs due to use in closure

And fixing it would require writing non-move closures as follows:

use ::std::{
    fs::File,
    io::Write,
};

fn foo (filename: String)
{
    let mut file =
        File::create(&filename)
            .unwrap_or_else({
                let filename = &filename;
                |err| panic!(
                    "Failed to create {:?}: {}", filename, err,
                )
            })
    ;
    let contents = "Hello, World!";
    file.write_all(contents.as_bytes())
        .unwrap_or_else({
            let filename = &filename;
            |err| panic!(
                "Failed to write {:?} into {:?}: {}",
                contents, filename, err,
            )
        })
    ;
}
1 Like

Ok, maybe there will eventually be some syntactic sugar added to make move lambdas less verbose in one-liners like in our case. Or I might just get used to it...

Btw, had no idea that you could wrap the lambda in a block and redeclare the variables like you just did in your last example. Good to know!