Determining whether the set is reflexive, symmetric, anti symmetric and transtitive

This is a discussion on Determining whether the set is reflexive, symmetric, anti symmetric and transtitive within the C++ Programming forums, part of the General Programming Boards category; I am having trouble finding out how to code this. I understand what each one is and know how to ...

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    10

    Determining whether the set is reflexive, symmetric, anti symmetric and transtitive

    I am having trouble finding out how to code this. I understand what each one is and know how to tell by looking but cannot figure out how to create functions to check whether it is either reflexive, symmetric, anti-symmetric, and/or transitive (it can be more than one). Here is the exact problem. Given a set of binary relations, determine whether the set is reflexive, symmetric, anti symmetric and/or transitive. Here are the sets:


    0 1 2 3
    0 0
    1 1
    2 2
    3 3

    x y z
    x y
    y z
    y y
    z z

    x y z
    x x
    y z
    x y
    z y
    x z
    y y
    z x
    y x
    z z

    1 2 3 4 5 6 7 8
    1 4
    1 7
    2 5
    2 8
    3 6
    4 7
    5 8
    6 6
    1 1
    2 2

  2. #2
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,528
    >I understand what each one is and know how to tell by looking but cannot figure out how to create functions to check whether it is either reflexive, symmetric, anti-symmetric, and/or transitive (it can be more than one).

    First do it by hand....
    Then put the exact same steps into your functions.
    Manasij Mukherjee | gcc-4.9.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  3. #3
    Registered User
    Join Date
    Nov 2011
    Posts
    10

    Transitive??

    I have got all of them but transitive now... I do not know how to include c in my functions.  Transitive means: If aRb and bRc, then aRc. Here is my reflexive function... How can I change them to make it test for transitive?

    Code:
    void reflexive(int a[], int sizeOfA, int b[], int sizeOfB){
        int i, j;
        bool test;
        bool hold = true;
    
    
        for(i = 0; i < sizeOfA; i++)
        {
            if(hold == true)
            {
                for(j = 0; j < sizeOfB;)
                {
                    if(b[j]==a[i] && b[j+1]==a[i])
                    {
                        hold = true;
                        break;
                    }
                    else
                    {
                        hold = false;
                        j++;
                    }
                }
            }
        }
        if(hold == true)
        {
            test = true;
            cout << "Reflextive - Yes" << endl;
        }
        else
        {
            test = false;
            cout << "Reflextive - No" << endl;
        }
    }

  4. #4
    Registered User
    Join Date
    Nov 2011
    Posts
    37
    why do you have && b[j+1]==a[i]?
    I believe the condition of b[j]==a[i] is enough.

    Anyway in reflexive the naive way is to check each 2 couples (let's say (a,b) and (b,c)) and then check if there is (a,c) pair).
    Of course there are much better ways.

  5. #5
    Registered User
    Join Date
    Nov 2011
    Posts
    10
    @walla- are you stating my reflexive does not work properly? Also, can you help me in the right direction for determining the transitive function? Thanks.

  6. #6
    Registered User
    Join Date
    Nov 2011
    Posts
    2
    To test if something is transitive you would need to use for loops. In a 2d arrary it would look like this. If M[i][j] = 1, and M[j][k] = 1, then M[i][k] = 1. If thats true it is transitive. Your reflexive is simply i != i for all i.

  7. #7
    Registered User
    Join Date
    Nov 2011
    Posts
    10
    @ bradzk - For my transitive function, your saying to use 3 for loops and pointers? Also, what is M? Your telling to use i,j,k. Also, what do you mean i != i for all i in my reflexive function?
    Last edited by ZING14; 11-15-2011 at 10:22 PM.

  8. #8
    Registered User
    Join Date
    Nov 2011
    Posts
    37
    Quote Originally Posted by ZING14 View Post
    @walla- are you stating my reflexive does not work properly? Also, can you help me in the right direction for determining the transitive function? Thanks.
    yes.
    00
    11
    22
    will give false in your reflexive function

  9. #9
    Registered User
    Join Date
    Nov 2011
    Posts
    10
    @walla - changing it to b[j]==a[i] still comes back false. So implement it by saying if (a,b) and (b,c), look for (a,c)? Can you give pseudo code of what you mean? Thanks.

  10. #10
    Registered User
    Join Date
    Nov 2011
    Posts
    37
    Don't worry for now about transitive, your reflexive function isn't right.
    First of all the definition of reflexive set is that each number x in the area will have (x,x) relation.
    So to build an appropriate reflexive function first you need to know all the elements in the area.
    Then you will need to check that for each one of them there is a (x,x) relation.

  11. #11
    Registered User
    Join Date
    Nov 2011
    Posts
    2
    If you use a 2d array then, matrix[i][i] = 1 for all i in the array, is reflexive.

  12. #12
    Registered User
    Join Date
    Nov 2011
    Posts
    10
    My new reflexive function :

    Code:
    void reflexive(int a[], int sizeOfA, int b[], int sizeOfB) 
    { 
      bool hold = true; 
     
      for(i = 0; i < sizeOfA && hold; ++i )  
           {      
             for( int j = 0; j < sizeOfB && hold; ++j )      
             {          
                int elemA = a[i];          
                int elemB = b[i];  
     
               if(a[i] == b[i]) 
               {            
                   hold = true; 
                   break; 
                } 
             } 
             if(hold == false) 
             { 
                 cout << "Reflexive - No" << endl; 
                  break; 
             } 
           } 
           if(hold == true) 
             cout << "Reflexive - Yes" << endl; 
      }

  13. #13
    Registered User
    Join Date
    Nov 2011
    Posts
    37
    This solution is not good.
    1. You don't use j.
    2. hold can not get false.
    May I suggest to compile and run examples on your function before posting it?
    I will suggest these simple examples for a start:

    1. (0,0),(1,1) - reflexive
    2. (0,0),(1,1),(1,2) - not reflexive
    3. (1,2),(2,1),(1,1),(2,2) - reflexive

    Hope it helps. Try and error is the best way to learn

  14. #14
    Registered User
    Join Date
    Nov 2011
    Posts
    10
    Ok, thank you for being patient with me walla. I believe this is close. I should be getting reflexive for sets 1 and 3. Although, it gave me reflexive for all of them which I know is wrong. Is one of my loops bad?

    Code:
    void reflexive(int a[], int sizeOfA, int b[], int sizeOfB)
    {
        bool hold = true;
        for(int i = 0; i < sizeOfA; ++i)
        {
            hold = false;
            for(int j = 0; j < sizeOfB; ++j)
            {
                if(a[i] == b[j]) 
                {
                    hold = true;
                    break;
                }
            }
            if(hold = false)
            {
                cout << "Reflexive - No" << endl;
                break;
            }
        }
        if(hold = true)
        {
            cout << "Reflexive - Yes" << endl;
        }
            
    }
    Last edited by ZING14; 11-16-2011 at 03:48 PM.

  15. #15
    Registered User
    Join Date
    Nov 2011
    Posts
    10
    I've modified it a bit but it wants me to create pointers to the objects a[i] and b[i] I don't know why.

    Code:
    void reflexive(int a[], int sizeOfA, int b[], int sizeOfB)
    {
    	bool hold = true;
    	for(int i = 0; i < sizeOfA; ++i)
    	{
    		int a = a[i];
    		int b = b[i];
    		hold = false;
    		for(int j = 0; j < sizeOfB; ++j)
    		{
    			if(a[j] == b)
    				if(b[j] == a)
    					hold = true;
    					break;
    		}
    		if(hold = false)
    		{
    			cout << "Reflexive - No" << endl;
    			break;
    		}
    	}
    	if(hold = true)
    	{
    		cout << "Reflexive - Yes" << endl;
    	}
    }

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. DataGridView symmetric values for the main diagonal ?
    By Borislav in forum C# Programming
    Replies: 0
    Last Post: 10-24-2011, 11:45 PM
  2. Replies: 17
    Last Post: 11-16-2006, 09:06 PM
  3. Anti-virus
    By Dragon227Slayer in forum Tech Board
    Replies: 4
    Last Post: 06-15-2004, 10:21 AM
  4. Anti-VB
    By BillBoeBaggins in forum A Brief History of Cprogramming.com
    Replies: 0
    Last Post: 01-07-2004, 04:05 PM
  5. Are you for MS or Anti-MS?
    By Fool in forum A Brief History of Cprogramming.com
    Replies: 39
    Last Post: 09-10-2001, 07:09 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21