How to verify Symmetric Relation?
To verify a symmetric relation do the following:
- Manually check for the existence of every bRa tuple for every aRb tuple in the relation.
- If any of the tuples does not exist then the relation is not symmetric else it is symmetric.
Follow the below illustration for a better understanding
Illustration:
Consider set A = { 1, 2, 3, 4 } and a relation R = { (1, 2), (1, 3), (2, 1), (3, 4), (3, 1) }
For the pair (1, 2) in R:
=> The reversed pair (2, 1) is present in the relation.
=> This pair satisfies the conditionFor the pair (1, 3) in R:
=> The reversed pair (3, 1) is present in the relation.
=> This pair satisfies the conditionFor the pair (2, 1) in R:
=> The reversed pair (1, 2) is present in the relation.
=> This pair satisfies the conditionFor the pair (3, 4) in R:
=> The reversed pair (4, 3) is not present in the relation.
=> This pair does not satisfy the conditionFor the pair (3, 1) in R:
=> The reversed pair (1, 3) is present in the relation.
=> This pair satisfies the conditionAs the pair (3, 4) does not satisfy the condition, the relation is not symmetric.
Below is the code implementation of the idea:
C++
#include <bits/stdc++.h> using namespace std; class Relation { public : bool checkSymmetric(set<pair< int , int > > R) { // Property 1 if (R.size() == 0) { return true ; } for ( auto i = R.begin(); i != R.end(); i++) { // Making a mirror tuple auto temp = make_pair(i->second, i->first); if (R.find(temp) == R.end()) { // If bRa tuple does not exists in relation // R return false ; } } // bRa tuples exists for all aRb in relation R return true ; } }; // Driver code int main() { // Creating relation R set<pair< int , int > > R; // Inserting tuples in relation R R.insert(make_pair(1, 1)); R.insert(make_pair(1, 2)); R.insert(make_pair(2, 1)); R.insert(make_pair(2, 3)); R.insert(make_pair(3, 2)); R.insert(make_pair(3, 4)); Relation obj; // R is not symmetric as (4, 3) tuple is not present if (obj.checkSymmetric(R)) { cout << "Symmetric Relation" << endl; } else { cout << "Not a Symmetric Relation" << endl; } return 0; } |
Java
// Java code to implement the approach import java.io.*; import java.util.*; class pair { int first, second; pair( int first, int second) { this .first = first; this .second = second; } } class GFG { static class Relation { boolean checkSymmetric(Set<pair> R) { // Property 1 if (R.size() == 0 ) { return true ; } for (var i : R) { // Making a mirror pair // Eg : (1, 2) => mirror pair = (2, 1) pair temp = new pair(i.second, i.first); if (!R.contains(temp)) { // If bRa tuple does not exists in // relation R return false ; } } // bRa tuples exists for all aRb in relation R return true ; } } public static void main(String[] args) { // Creating relation R Set<pair> R = new HashSet<>(); // Inserting tuples in relation R R.add( new pair( 1 , 1 )); R.add( new pair( 1 , 2 )); R.add( new pair( 2 , 1 )); R.add( new pair( 2 , 3 )); R.add( new pair( 3 , 2 )); R.add( new pair( 3 , 4 )); Relation obj = new Relation(); // R is not symmetric as (4, 3) tuple is not present if (obj.checkSymmetric(R)) { System.out.println( "Symmetric Relation" ); } else { System.out.println( "Not a Symmetric Relation" ); } } } // This code is contributed by lokeshmvs21. |
Python3
class Relation: def checkSymmetric( self , R): # Property 1 if len (R) = = 0 : return True for i in R: if (i[ 1 ], i[ 0 ]) not in R: # If bRa tuple does not exists in relation R return False # bRa tuples exists for all aRb in relation R return True # Driver code if __name__ = = '__main__' : # Creating relation R R = {( 1 , 1 ), ( 1 , 2 ), ( 2 , 1 ), ( 2 , 3 ), ( 3 , 2 ), ( 3 , 4 )} obj = Relation() # R is not symmetric as (4, 3) tuple is not present if obj.checkSymmetric(R): print ( "Symmetric Relation" ) else : print ( "Not a Symmetric Relation" ) |
C#
// C# code to implement the approach using System; using System.Collections.Generic; class pair { public int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } public class GFG { class Relation { public bool checkSymmetric(HashSet<pair> R) { // Property 1 if (R.Count == 0) { return true ; } foreach ( var i in R) { // Making a mirror pair // Eg : (1, 2) => mirror pair = (2, 1) pair temp = new pair(i.second, i.first); if (!R.Contains(temp)) { // If bRa tuple does not exists in // relation R return false ; } } // bRa tuples exists for all aRb in relation R return true ; } } static public void Main() { // Code // Creating relation R HashSet<pair> R = new HashSet<pair>(); // Inserting tuples in relation R R.Add( new pair(1, 1)); R.Add( new pair(1, 2)); R.Add( new pair(2, 1)); R.Add( new pair(2, 3)); R.Add( new pair(3, 2)); R.Add( new pair(3, 4)); Relation obj = new Relation(); // R is not symmetric as (4, 3) tuple is not present if (obj.checkSymmetric(R)) { Console.WriteLine( "Symmetric Relation" ); } else { Console.WriteLine( "Not a Symmetric Relation" ); } } } // This code is contributed by lokesh |
Javascript
class Relation { constructor() {} checkSymmetric(R) { // Property 1 if (R.size === 0) { return true ; } for (const i of R) { // Making a mirror tuple const temp = [i[1], i[0]]; if (!R.has(temp)) { // If bRa tuple does not exists in relation // R return false ; } } // bRa tuples exists for all aRb in relation R return true ; } } // Driver code function main() { // Creating relation R const R = new Set(); // Inserting tuples in relation R R.add([1, 1]); R.add([1, 2]); R.add([2, 1]); R.add([2, 3]); R.add([3, 2]); R.add([3, 4]); const obj = new Relation(); // R is not symmetric as (4, 3) tuple is not present if (obj.checkSymmetric(R)) { console.log( "Symmetric Relation" ); } else { console.log( "Not a Symmetric Relation" ); } } main(); // This code is contributed by akashish__ |
Not a Symmetric Relation
Time Complexity: O(N * log N) where N is the number of tuples in the relation
Auxiliary Space: O(1)
Symmetric Relation on a Set
A relation is a subset of the cartesian product of a set with another set. A relation contains ordered pairs of elements of the set it is defined on. To learn more about relations refer to the article on “Relation and their types“.
Contact Us