# Cartesian product

Discussion in 'C++' started by zfareed@umd.umich.edu, Feb 11, 2007.

1. ### Guest

I have a program that creates two sets, one thru user interaction and
the other with the use of an array. Can anyone help with coding for
finding the cartesian product of the two sets; i.e a relation?

#include <iostream>
#include <set>
#include <algorithm>

using namespace std;

int main()
{

int arr[] = {1,3,5,7,9,11,13,15,17,19,21,23,25,27,29};
int arrSize = sizeof(arr) / sizeof(int);
set<int> A;
set<int> B(arr,arr+arrSize);

int num1=0;
int num2=0;

for(int x=0;x<20;x++)
{
cout << "Please enter an even integer less than 100:" << endl;
cin >> num1;
if(A.find(num1) != A.end())

cout << num1 << " has already been entered!"
<< endl;

else if((num1 % 2) != 0)
cout << "That is not an even number!" << endl;
else
A.insert(num1);
}

cout << endl;

cout << "Set A has " << A.size() << "elements." <<endl;
cout << "Set B has " << B.size() << "elements." << endl;
system("pause");

return 0;

}

I have included the code below I got from a site that suggests
creating a struct pair and defining an operator, but I do not
understand it.

struct Pair{
int i;
int j;
};
int operator==(const Pair& p1,const Pair& p2){
return p1.i==p2.i && p1.j==p2.j;
}
set<pair> result;

, Feb 11, 2007

2. ### John HarrisonGuest

wrote:
> I have a program that creates two sets, one thru user interaction and
> the other with the use of an array. Can anyone help with coding for
> finding the cartesian product of the two sets; i.e a relation?
>
> #include <iostream>
> #include <set>
> #include <algorithm>
>
> using namespace std;
>
> int main()
> {
>
> int arr[] = {1,3,5,7,9,11,13,15,17,19,21,23,25,27,29};
> int arrSize = sizeof(arr) / sizeof(int);
> set<int> A;
> set<int> B(arr,arr+arrSize);
>
> int num1=0;
> int num2=0;
>
> for(int x=0;x<20;x++)
> {
> cout << "Please enter an even integer less than 100:" << endl;
> cin >> num1;
> if(A.find(num1) != A.end())
>
> cout << num1 << " has already been entered!"
> << endl;
>
> else if((num1 % 2) != 0)
> cout << "That is not an even number!" << endl;
> else
> A.insert(num1);
> }
>
> cout << endl;
>
> cout << "Set A has " << A.size() << "elements." <<endl;
> cout << "Set B has " << B.size() << "elements." << endl;
> system("pause");
>
> return 0;
>
>
>
>
> }
>
> I have included the code below I got from a site that suggests
> creating a struct pair and defining an operator, but I do not
> understand it.
>
> struct Pair{
> int i;
> int j;
> };
> int operator==(const Pair& p1,const Pair& p2){
> return p1.i==p2.i && p1.j==p2.j;
> }
> set<pair> result;
>

I'm not sure about that code either.

A catesian product is a set of pairs. Your sets are sets of integers so
your cartesian product is a set of pairs of integers. So you do need
something like this

struct Pair
{
int x;
int y;
};

set<Pair> cartesian_product;

But, it is a rule of the C++ set class that any element that you want to
be a member of a set must have the operator< defined (a better name for
set in C++ would be ordered_set, because its an ordered set you need to
define operator<).

So you must write

bool operator<(const Pair& p1, const Pair& p2)
{
...
}

That's what is wrong with the code you posted it defines operator== not
operator<. It doesn't matter how you define operator<, it's not needed
for your purposes, it's just something you must define to make set<Pair>
work. However (again rules of C++) you define operator< it must impose a
'strict weak ordering' on Pair (you sound reasonably mathematical so
I'll not define that). Here's on definition that does that.

bool operator<(const Pair& p1, const Pair& p2)
{
return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
}

That should be enough for you to get a set of Pair's working. Now all
you have to do is write the code to form the catesian product, that is
just a couple of for loops one inside the other.

Hope this helps.

John

John Harrison, Feb 11, 2007

3. ### Kai-Uwe BuxGuest

wrote:

> I have a program that creates two sets, one thru user interaction and
> the other with the use of an array. Can anyone help with coding for
> finding the cartesian product of the two sets; i.e a relation?
>
> #include <iostream>
> #include <set>
> #include <algorithm>
>
> using namespace std;
>
> int main()
> {
>
> int arr[] = {1,3,5,7,9,11,13,15,17,19,21,23,25,27,29};
> int arrSize = sizeof(arr) / sizeof(int);
> set<int> A;
> set<int> B(arr,arr+arrSize);
>
> int num1=0;
> int num2=0;
>
> for(int x=0;x<20;x++)
> {
> cout << "Please enter an even integer less than 100:" << endl;
> cin >> num1;
> if(A.find(num1) != A.end())
>
> cout << num1 << " has already been entered!"
> << endl;
>
> else if((num1 % 2) != 0)
> cout << "That is not an even number!" << endl;
> else
> A.insert(num1);
> }
>
> cout << endl;
>
> cout << "Set A has " << A.size() << "elements." <<endl;
> cout << "Set B has " << B.size() << "elements." << endl;
> system("pause");
>
> return 0;
>
>
>
>
> }
>
> I have included the code below I got from a site that suggests
> creating a struct pair and defining an operator, but I do not
> understand it.
>
> struct Pair{
> int i;
> int j;
> };
> int operator==(const Pair& p1,const Pair& p2){
> return p1.i==p2.i && p1.j==p2.j;
> }
> set<pair> result;

Consider using std:air<int,int> instead. The advantage is that is comes
with a correctly defined operator== and operator< so that you can use it
with std::set<>, i.e.,

std::set< std:air<int,int> >

will be a set of ordered pairs of integers. Just what the doctor ordered.

Best

Kai-Uwe Bux

Kai-Uwe Bux, Feb 11, 2007