Velocity Reviews > C++ > Cartesian product

# Cartesian product

zfareed@umd.umich.edu
Guest
Posts: n/a

 02-11-2007
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;

John Harrison
Guest
Posts: n/a

 02-11-2007
http://www.velocityreviews.com/forums/(E-Mail Removed) 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

Kai-Uwe Bux
Guest
Posts: n/a

 02-11-2007
(E-Mail Removed) 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;

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