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
    #1
    1. Advertising

  2. 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
    #2
    1. Advertising

  3. Kai-Uwe Bux Guest

    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::pair<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::pair<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
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. deancoo

    cartesian product...

    deancoo, Feb 28, 2005, in forum: C++
    Replies:
    4
    Views:
    2,301
    Matt Bitten
    Feb 28, 2005
  2. Thorsten Kampe

    Cartesian Product of two lists (itertools)

    Thorsten Kampe, Jan 25, 2009, in forum: Python
    Replies:
    3
    Views:
    419
    Mark Wooding
    Jan 26, 2009
  3. Brad
    Replies:
    9
    Views:
    359
  4. walter a kehowski

    cartesian product

    walter a kehowski, Aug 7, 2005, in forum: Ruby
    Replies:
    26
    Views:
    319
    tony summerfelt
    Aug 10, 2005
  5. walter a kehowski

    cartesian product - next to last version

    walter a kehowski, Aug 11, 2005, in forum: Ruby
    Replies:
    11
    Views:
    211
    Brian Schröder
    Aug 13, 2005
Loading...

Share This Page