Generate all non-redundant tuple combinations of indices

help
1

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?

2

Itertools::tuple_combinations

6 Likes
3

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

1 Like
4

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
5

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?

6

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
7

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.

8

:+1:

9

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
10

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!

11

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.