cartesian product of two vector spaces

Question

A few days back I found an interesting problem which reads the following:

Given two vector spaces generate the resulting set of its cartesian product. \begin{gather} \text{Let: } \mathcal{V}, \mathcal{W} \text{ be vector spaces}\\ \mathcal{V} \times \mathcal{W} = \{ (v,w) \mid v \in \mathcal{V} \land w \in \mathcal{W} \} \end{gather}

• Hint 1: A vector space is a set of elements called vectors which accomplishes some properties
• Hint 2: Design the solution for finite vector spaces
• Tip 1: It is recommended to use structures
• Constraint: You are forbidden to use any stl class

I solved this problem with the next approach:

struct vector_pair
{
 double *vector_a;
 double *vector_b;
 size_t a_dimension;
 size_t b_dimension;
};
struct cartesian_product_set
{
 vector_pair *pairs;
 size_t pairs_number;
};
cartesian_product_set vector_spaces_cartesian_product(double **space_v, size_t v_vectors,
 size_t v_dimension, double **space_w, size_t w_vectors, size_t w_dimension)
{
 cartesian_product_set product_set{new vector_pair[v_vectors * w_vectors], v_vectors * w_vectors};
 
 for (size_t i = 0, j, k = 0; i < v_vectors; i++)
 for (j = 0; j < w_vectors; j++)
 product_set.pairs[k++] = vector_pair{space_v[i], space_w[j], v_dimension, w_dimension};
 return product_set;
}

How could I improve this code if possible?

Thank you.

• G. Sliepen: Are you sure the result should contain vector_pairs? The question might also suggest you have to return a single vector of dimension a_dimension + b_dimension.
• sɪʒɪhɪŋ βɪstɦa kxɐll: A cartesian product generates pairs, it doesn't operate the objects which it takes. It is like a combinatorial of each element in V with each element in W by pairs; The dimension of those vectors doesn't affect the product.

Answer 1

1. const-correctness
2. use references in favor of pointers where possible
3. The fact that you leave the obligation to free the memory that you allocate to the caller is generally not a good practice
4. a common pattern in your code is that you have pointers to arrays and their length - why not make a structure to bundle them up?
5. try to make use of iterators and range-based-for-loops when you don't really need the index (which you don't in your example)
6. since we don't really care about the type of the elements in a vector space you could use templates to generalize your algorithm

And just to see if it would be possible, I tried to come up with a compile-time version of the algorithm:

template<typename T>
struct pair
{
 T first;
 T second;
};
template<std::size_t N, typename T>
struct cvp
{
 pair<T> pairs[N];
};
template <typename T, size_t NV, size_t NW>
auto get_cvp(const T (&vs)[NV], const T (&ws)[NW])
{
 cvp<NV*NW, T> result;
 auto it_pairs = std::begin(result.pairs);
 for (const auto v : vs) {
 for (const auto w : ws) {
 *(it_pairs++) = {v, w};
 }
 }
 return result;
}

you can try the code here: https://godbolt.org/z/e8GvEf

• sɪʒɪhɪŋ βɪstɦa kxɐll: Thank you so much, your explanation is concise and you provide an actual example with templates. The only thing I would change would be cvp by cartesian_product because as this algorithm generalizates the pairs it is not different from a cartesian between two sets (which is more abstract).