Task 2: Set Product
Task
In this exercise, you are going to implement a function which computes the n-fold Cartesian product for sets. The n-fold Cartesian product is a way to combine multiple sets of items. Imagine you have multiple sets, denoted as \(A_1, A_2, ..., A_n\). The n-fold Cartesian product is like taking one item from each set and combining them into a new set.
For example, let's say you have two sets:
\[ A_1 = \{a,b,c\} \text{ and } A_2 = \{ x, y, z \} \]
The Cartesian product of these two sets would be a new set that contains all possible combinations of one item from \(A_1\) and one item from \(A_2\):
\[ A_1 \times A_2 = \{(a,x),(a,y),(a,z),(b,x),(b,y),(b,z),(c,x),(c,y),(c,z)\} \]
In general, for any two sets \(A\) and \(B\), the Cartesian product \(A times B\) is defined as:
\[ A \times B \{(a,b) | a \in A \text{ and } b \in B\} \]
This can be generalized to the n-fold Cartesian product. For any \(n\) sets \(A_1, A_2, ... , A_n\), the n-fold Cartesian product is defined as:
\[ A_1 \times A_2 \times ... \times A_n = \{(a_1, a_2, ..., a_n) | a_i \in A_i \text{ for all } i = 1, 2, ... , n\} \]
Note: This task naturally lends itself to a recursive implementation.
The Set class
A set class is implemented in set.h and set.ipp. This class
implements a number of useful operations on sets. *For an overview of
its functionalities, please refer to this week's Power Set code
example*. Note that you do not need to understand any of the code in
set.h and set.ipp in order to use it!
Input & Output
When the program starts, you are first prompted to enter the number of
sets. Then, you are prompted to enter each set. Sets are entered on a
single line using the format
<number of char elements> <elements separated by spaces>.
Once all sets are entered, the set product is computed using the
set_product function. Finally, the resulting set is printed to the
console.
Example
Number of sets: 2
Set 0: 3 a b c
Set 1: 2 x y
Product Set:
{ax,ay,bx,by,cx,cy}Note: Each input set is a set of char elements. At least 1 set must be inputted.
Solution
#include <iterator>
#include <string>
#include <vector>
#include "set.h"
#include "solution.h"
StringSet set_product(const std::vector<CharSet> &sets) {
StringSet res;
StringSet ram;
if (sets.size() == 1) {
for (int i = 0; i < sets[0].size(); ++i) {
std::string j(1, sets[0][i]);
res.insert(j);
}
return res;
}
CharSet first_subset = sets[0];
std::vector<CharSet> remaining_set(sets.begin() + 1, sets.end());
StringSet res_subset = set_product(remaining_set);
for (char char_first_subset : first_subset.elements()) {
for (std::string str_res_subset : res_subset.elements()) {
res.insert(std::string(1, char_first_subset) + str_res_subset);
}
}
return res;
}Made by JirR02 in Switzerland 🇨🇭