Teeing an iterator at every iteration

Question

I would like to iterate over the Cartesian product of every pair of elements in a list:

let x = vec![1, 2, 3, 4];
for i in 0..3 {
    for j in i + 1..4 {
        println!("{} {}", x[i], x[j]);
    }
}

1 2
1 3
1 4
2 3
2 4
3 4

So far so good. I wanted to attempt the same thing with an iterator. My idea was to grab an iterator for the outer loop, then clone and skip one element for the inner loop. This did not work well:

let outer = x.iter();
for pt1 in outer.clone() {
    for pt2 in (&outer).clone().skip(1) {
        println!("{} {}", pt1, pt2);
   }
}

Since I had to clone the outer iterator to tee it, the inner is going off the original state, not the current state of the outer iterator:

1 2
1 3
1 4
2 2
2 3
2 4
3 2
3 3
3 4
4 2
4 3
4 4

How can I tell rust to replicate the behavior of the range loops with non-consuming iterators over the elements of the collection?

Related question I found, but the answer still uses iterators over ranges instead of the items themselves: How do I idiomatically compare each item in a list to every other item?.

Answer 1

@brian61354270 already mentioned in the comments, that what you want is not really a cartesian product. Otherwise an obvious answer would be to use itertools::iproduct!.

Going off of your main question:

I wanted to attempt the same thing with an iterator.

Since we can assume x: Vec, and you want to produce indices. Then we can produce a cartesian product of the indices using the range 0..x.len().

let n = x.len();
let indices = (0..n)
    .flat_map(move |x| std::iter::repeat(x).zip(0..n));

Now, to get the combinations then we can modify it just slightly (similarly to your + i for loop):

let n = x.len();
let indices = (0..n)
    .flat_map(move |x| std::iter::repeat(x).zip((x + 1)..n));

Then iterating over indices:

for (i0, i1) in indices {
    let (x, y) = (x[i0], x[i1]);
    println!("{x} {y}");
}

Will produce:

1 2   
1 3
1 4
2 3
2 4
3 4

Alternatively, you can also use itertools's combinations() to achieve the same:

let indices = (0..n).combinations(2);

for i0i1 in indices {
    let (i0, i1) = (i0i1[0], i0i1[1]);
    let (x, y) = (x[i0], x[i1]);
    println!("{x} {y}");
}

---

Since you don't want to map indices to items, then you could do something like this:

let mut iter = x.iter();
let pairs = std::iter::from_fn(|| {
    let next = iter.next()?;
    let iter = iter.clone();
    Some(std::iter::repeat(next).zip(iter))
})
.flatten();

Alternatively, written like this:

let mut iter = x.iter();
let pairs = std::iter::from_fn(|| {
    iter.next().map(|next| {
        let iter = iter.clone();
        std::iter::repeat(next).zip(iter)
    })
})
.flatten();

Where iterating for (x, y) in pairs yields the same as before.

I would however consider both a lot harder to read. At least when compared to using indices and then .map(|(i0, i1)| (x[i0], x[i1])).