How can I compute the Cartesian product of a vector with itself N times?

Question

I'm looking for a function with the signature fn product(vector: &Vec<i32>, n: &i32) -> Vec<Vec<i32>> or similar. An example:

assert_eq!(
    product(vec![1, 2, 3, 4], 2),
    [
        [1, 1],
        [1, 2],
        [1, 3],
        [1, 4],
        [2, 1],
        [2, 2],
        [2, 3],
        [2, 4],
        [3, 1],
        [3, 2],
        [3, 3],
        [3, 4],
        [4, 1],
        [4, 2],
        [4, 3],
        [4, 4]
    ],
)

I have tried using iproduct from the itertools crate:

use itertools::iproduct; // 0.10.0

fn product(vector: &Vec<i32>, n: &i32) -> Vec<Vec<i32>> {
    let mut result = Vec::new();

    for _ in 0..*n {
        result = iproduct!(result.iter(), vector.iter()).collect();
    }

    result
}

Which produces this error:

error[E0277]: a value of type `Vec<_>` cannot be built from an iterator over elements of type `(&_, &i32)`
 --> src/lib.rs:7:58
  |
7 |         result = iproduct!(result.iter(), vector.iter()).collect();
  |                                                          ^^^^^^^ value of type `Vec<_>` cannot be built from `std::iter::Iterator<Item=(&_, &i32)>`
  |
  = help: the trait `FromIterator<(&_, &i32)>` is not implemented for `Vec<_>`

How do I solve this problem?

Alexey Romanov · Accepted Answer · 2021-01-18T19:40:57.363

What type do you expect result to be, exactly? For it to be the return value, it has to be Vec<Vec<i32>>, right? But then iproduct!(result.iter(), vector.iter()) returns an Iterator<Item = (&Vec<i32>, &i32)> (you can see that by specifying the type of result explicitly) and it assigns a Vec<(&Vec<i32>, &i32)> to result, which can't work. So you need to map an (&Vec<i32>, &i32) to a Vec<i32> first.
At the start, result is empty so its product with anything is empty. It needs to contain a single element instead. What should that element be?
There is little point to taking n by reference; similarly, it's preferred to accept a slice &[i32] instead of a &Vec<i32>

If you fix all of this, you get

S  
o  
m  
e  

s  
p  
o  
i  
l  
e  
r  

s  
p  
a  
c  
e  

f
o
r

y
o
u

t
o

t
r
y

y
o
u
r
s
e
l
f

Playground

use itertools::iproduct;

fn product(vector: &[i32], n: i32) -> Vec<Vec<i32>> {
    let mut result: Vec<Vec<i32>> = vec![vec![]];

    for _ in 0..n {
        result = iproduct!(result.iter(), vector.iter())
            .map(|(v, x)| {
                let mut v1 = v.clone();
                v1.push(*x);
                v1
            })
            .collect();
    }

    result
}

I'd go with flat_map instead of using iproduct myself.

How can I compute the Cartesian product of a vector with itself N times?

1 Answers1