How to verify Asymmetric Relation?
To verify asymmetric relation follow the below method:
- Manually check for the existence of every bRa tuple for every aRb tuple in the relation.
- If any of the tuples exist or (a = b) then the relation is not asymmetric else it is asymmetric.
Follow the below illustration for a better understanding:
Illustration:
Consider set A = { 1, 2, 3, 4 } and relation R = { (1, 2), (1, 3), (2, 3), (3, 4) }
For (1, 2) in set R:
=> The reversed pair (2, 1) is not present in R.
=> This satisfies the condition.For (1, 3) in set R:
=> The reversed pair (3, 1) is not present in R.
=> This satisfies the condition.For (2, 3) in set R:
=> The reversed pair (3, 2) is not present in R.
=> This satisfies the condition.For (3, 4) in set R:
=> The reversed pair (4, 3) is not present in R.
=> This satisfies the condition.So R is an asymmetric relation.
Below is the code implementation of the idea:
C++
#include <bits/stdc++.h> using namespace std; class Relation { public : bool checkAsymmetric(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 or aRa tuple does exists in // relation R return false ; } } // bRa or aRa tuples does not exists for all aRb in // relation R return true ; } }; int main() { // Creating relation R set<pair< int , int > > R; // Inserting tuples in relation R R.insert(make_pair(1, 2)); R.insert(make_pair(2, 3)); R.insert(make_pair(3, 4)); Relation obj; // R is asymmetric as bRa tuple is not present if (obj.checkAsymmetric(R)) { cout << "Asymmetric Relation" << endl; } else { cout << "Not a Asymmetric 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 checkAsymmetric(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 or aRa tuple does exists in // relation R return false ; } } // bRa or aRa tuples does not 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 , 2 )); R.add( new pair( 2 , 3 )); R.add( new pair( 3 , 4 )); Relation obj = new Relation(); // R is asymmetric as bRa tuple is not present if (obj.checkAsymmetric(R)) { System.out.println( "Asymmetric Relation" ); } else { System.out.println( "Not a Asymmetric Relation" ); } } } // This code is contributed by lokeshmvs21. |
Python3
class Relation: def checkAsymmetric( self , R): # Property 1 if len (R) = = 0 : return True for i in R: if (i[ 1 ], i[ 0 ]) in R: # If bRa or aRa tuple does exist in relation R return False # bRa or aRa tuples does not exist for all aRb in relation R return True # Driver code if __name__ = = '__main__' : # Creating relation R R = {( 1 , 2 ), ( 2 , 3 ), ( 3 , 4 )} obj = Relation() # R is asymmetric as bRa tuple is not present if obj.checkAsymmetric(R): print ( "Asymmetric Relation" ) else : print ( "Not a Asymmetric 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 checkAsymmetric(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 or aRa tuple does exists in // relation R return false ; } } // bRa or aRa tuples does not 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, 2)); R.Add( new pair(2, 3)); R.Add( new pair(3, 4)); Relation obj = new Relation(); // R is asymmetric as bRa tuple is not present if (obj.checkAsymmetric(R)) { Console.WriteLine( "Asymmetric Relation" ); } else { Console.WriteLine( "Not a Asymmetric Relation" ); } } } // This code is contributed by lokesh. |
Javascript
class Relation { constructor() {} checkAsymmetric(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 or aRa tuple does exists in // relation R return false ; } } // bRa or aRa tuples does not exists for all aRb in // relation R return true ; } } function main() { // Creating relation R const R = new Set(); // Inserting tuples in relation R R.add([1, 2]); R.add([2, 3]); R.add([3, 4]); const obj = new Relation(); // R is asymmetric as bRa tuple is not present if (obj.checkAsymmetric(R)) { console.log( "Asymmetric Relation" ); } else { console.log( "Not a Asymmetric Relation" ); } } main(); // This code is contributed by akashish__ |
Asymmetric Relation
Time Complexity: O(N * log N), Where N is the number of elements in relation R.
Auxiliary Space: O(1)
Asymmetric 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