Member Avatar for zing14

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 Contributors
  • 3 Replies
  • 4K Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by zing14

Dani AI

Generated

A reliable way to test these properties is to represent the relation as a membership test, not by scanning a flat array. Build an index for the universe U, construct an N x N boolean matrix M where M[i][j] is true iff (u_i, u_j) is in the relation, then check the properties directly on M. This avoids off‑by‑two errors when treating pairs, inner loops that never advance, and brittle equality checks. Formal definitions of reflexive, symmetric, antisymmetric, and transitive relations are summarized in Properties of binary relations. For the C++ containers used below, see std::unordered_map and std::vector.

#include <vector>
#include <unordered_map>
using namespace std;

template<class T>
vector<vector<bool>> buildMatrix(const vector<T>& U,
                                 const vector<pair<T,T>>& R) {
    unordered_map<T,int> id;
    for (int i = 0; i < (int)U.size(); ++i) id[U[i]] = i;
    vector<vector<bool>> M(U.size(), vector<bool>(U.size(), false));
    for (auto [a,b] : R) M[id[a]][id[b]] = true;
    return M;
}

bool is_reflexive(const vector<vector<bool>>& M){
    for (int i = 0; i < (int)M.size(); ++i) if (!M[i][i]) return false;
    return true;
}
bool is_symmetric(const vector<vector<bool>>& M){
    for (int i = 0; i < (int)M.size(); ++i)
        for (int j = i+1; j < (int)M.size(); ++j)
            if (M[i][j] != M[j][i]) return false;
    return true;
}
bool is_antisymmetric(const vector<vector<bool>>& M){
    for (int i = 0; i < (int)M.size(); ++i)
        for (int j = 0; j < (int)M.size(); ++j)
            if (i != j && M[i][j] && M[j][i]) return false;
    return true;
}
bool is_transitive(const vector<vector<bool>>& M){
    int n = (int)M.size();
    for (int i = 0; i < n; ++i)
        for (int k = 0; k < n; ++k) if (M[i][k])
            for (int j = 0; j < n; ++j)
                if (M[k][j] && !M[i][j]) return false;
    return true;
}

Tips grounded in this thread: treat each ordered pair as two adjacent values when building R (e.g., rel[2k], rel[2k+1]), pass correct sizes (|U| and number of pairs), and avoid inner loops that never increment their index.

Recommended Answers

All 3 Replies

Member Avatar for thines01

What compiler are you using?

Member Avatar for zing14

Here is what I have come up with but my functions are not working properly because I am getting false for the first set being reflexive when it should be coming back true. Also, I can't even get my transitive started.. Any help??

#include <iostream>

using namespace std;

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])
				{
					hold = true;
					break;
				}
				else
				{
					hold = false;
					cout << "Reflexive - No" << endl;
					break;
				}
			}
		}
	}
	if(hold == true)
	{
		test = true;
		cout << "Reflextive - Yes" << endl;
	}
}

void charReflexive(char a[], int sizeOfA, char 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])
				{
					hold = true;
					break;
				}
				else
				{
					hold = false;
					cout << "Reflexive - No" << endl;
					break;
				}
			}
		}
	}
	if(hold == true)
	{
		test = true;
		cout << "Reflextive - Yes" << endl;
	}
}

void symmetric(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(a[i] == a[j] && a[i+1] == a[j-1])
				{
					hold = true;
					break;
				}
				else
				{
					hold = false;
					cout << "Symmetric - No" << endl;
					break;
				}
			}
		}
	}
	if(hold == true)
	{
		test = true;
		cout << "Symmetric - Yes" << endl;
	}
}

void charSymmetric(char a[], int sizeOfA, char 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(a[i] == a[j] && a[i+1] == a[j-1])
				{
					hold = true;
					break;
				}
				else
				{
					hold = false;
					cout << "Symmetric - No" << endl;
					break;
				}
			}
		}
	}
	if(hold == true)
	{
		test = true;
		cout << "Symmetric - Yes" << endl;
	}
}

void antiSymmetric(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(a[i] <= b[j] && b[j] <= a[i])
				{
					hold = true;
					break;
				}
				else
				{
					hold = false;
					cout << "Antisymmetric - No" << endl;
					break;
				}
			}
		}
	}
	if(hold == true)
	{
		test = true;
		cout << "Antisymmetric - Yes" << endl;
	}
}

void charAntiSymmetric(char a[], int sizeOfA, char 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(a[i] <= b[j] && b[j] <= a[i])
				{
					hold = true;
					break;
				}
				else
				{
					hold = false;
					cout << "Antisymmetric - No" << endl;
					break;
				}
			}
		}
	}
	if(hold == true)
	{
		test = true;
		cout << "AntiSymmetric - Yes" << endl;
	}
}

void transitive(int a[], int sizeOfA, int b[], int sizeOfB)
{

}

void charTransitive(char a[], int sizeOfA, char b[], int sizeOfB)
{

}


int main()
{
	char keepGoing = 'y';
    while (keepGoing=='y') {
	
	int set1[4] = {0, 1, 2, 3};
	int rel1[8] = {0, 0, 1, 1, 2, 2, 3, 3};
	cout << "Set 1: " << endl;
	reflexive(set1, 3, rel1, 4);
	symmetric(set1, 3, rel1, 4);
	antiSymmetric(set1, 3, rel1, 4);

	cout << endl;
	char x, y, z;
	char set2[4] = {'x', 'y', 'z'};
	char rel2[8] = {'x', 'y', 'y', 'z', 'y', 'y', 'z', 'z'};
	cout << "Set 2: " << endl;
	charReflexive(set2, 4, rel2, 8);
	charSymmetric(set2, 4, rel2, 8);
	charAntiSymmetric(set2, 4, rel2, 8);

	cout << endl;
	char set3[3] = {'x', 'y', 'z'};
	char rel3[18] = {'x', 'x', 'y', 'z', 'x', 'y', 'z', 'y', 'x', 
					 'z', 'y', 'y', 'z', 'x', 'y', 'x', 'z', 'z'};
	cout << "Set 3: " << endl;
	charReflexive(set3, 3, rel3, 18);
	charSymmetric(set3, 3, rel3, 18);
	charAntiSymmetric(set3, 3, rel3, 18);

	cout << endl;
	int set4[8] = {1, 2, 3, 4, 5, 6, 7, 8};
	int rel4[20] = {1, 7, 2, 5, 2, 8, 3, 6, 4, 7, 5, 8, 6, 6, 1, 1,
					2, 2};
	cout << "Set 4: " << endl;
	reflexive(set4, 8, rel4, 20);
	symmetric(set4, 8, rel4, 20);
	antiSymmetric(set4, 8, rel4, 20);

	cout << endl << "Would you like to test it again? (y/n): ";
    cin >> keepGoing;
	}
	
	return 0;
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.