How to verify an Anti-Symmetric Relation?
To verify anti-symmetric relation:
- Manually check for the existence of every bRa tuple for every aRb tuple (if a ≠ b) in the relation.
- If any of the tuples exist then the relation is not anti-symmetric. Otherwise, it is anti-symmetric.
Follow the below illustration for a better understanding
Consider set A = { 1, 2, 3, 4 } and a relation R = { (1, 2), (1, 3), (2, 3), (3, 4), (4, 4) }
For (1, 2) in R:
=> The reversed pair (2, 1) is not present.
=> This satisfies the condition.For (1, 3) in R:
=> The reversed pair (3, 1) is not present.
=> This satisfies the condition.For (2, 3) in R:
=> The reversed pair (3, 2) is not present.
=> This satisfies the condition.For (3, 4) in R:
=> The reversed pair (4, 3) is not present.
=> This satisfies the condition.For (4, 4) in R:
=> The reversed pair (4, 4) is present but see here both the elements of the tuple are same.
=> So this also satisfies the condition.So R is an anti-symmetric relation.
Below is the code implementation of the idea:
C++
#include <bits/stdc++.h> using namespace std; class Relation { public : bool checkAntiSymmetric(set<pair< int , int > > R) { // Property 1 if (R.size() == 0) { return true ; } for ( auto i = R.begin(); i != R.end(); i++) { if (i->second != i->first) { // Not a aRa tuple // making a mirror tuple auto temp = make_pair(i->second, i->first); if (R.find(temp) != R.end()) { // If bRa tuple exists in relation R return false ; } } } // bRa 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, 1)); R.insert(make_pair(1, 2)); R.insert(make_pair(2, 3)); R.insert(make_pair(3, 4)); Relation obj; // R is anti-symmetric if (obj.checkAntiSymmetric(R)) { cout << "Anti-Symmetric Relation" << endl; } else { cout << "Not a Anti-Symmetric Relation" << endl; } return 0; } |
Java
// Java code implementation for the above 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 checkAntiSymmetric(Set<pair> R) { // Property 1 if (R.size() == 0 ) { return true ; } for (var i : R) { int one = i.first; int two = i.second; if (one != two) { // Not a aRa tuple if (R.contains( new pair(two, one))) { // If bRa tuple does exists in // relation R return false ; } } } // bRa 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 , 1 )); R.add( new pair( 1 , 2 )); R.add( new pair( 2 , 3 )); R.add( new pair( 3 , 4 )); Relation obj = new Relation(); // R is anti-symmetric if (obj.checkAntiSymmetric(R)) { System.out.println( "Anti-Symmetric Relation" ); } else { System.out.println( "Not a Anti-Symmetric Relation" ); } } } // This code is contributed by lokeshmvs21. |
Python3
class Relation: def checkAntiSymmetric( self , R): # Property 1 if len (R) = = 0 : return True for i in R: if i[ 0 ] ! = i[ 1 ]: # Not a aRa tuple if (i[ 1 ], i[ 0 ]) in R: # If bRa tuple does exists in relation R return False # bRa tuples does not exists for all aRb in relation R return True # Driver code if __name__ = = '__main__' : # Creating relation R R = {( 1 , 1 ), ( 1 , 2 ), ( 2 , 3 ), ( 3 , 4 )} obj = Relation() # R is anti-symmetric if obj.checkAntiSymmetric(R): print ( "Anti-Symmetric Relation" ) else : print ( "Not a Anti-Symmetric Relation" ) |
C#
// C# code implementation for the above 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 checkAntiSymmetric(HashSet<pair> R) { // Property 1 if (R.Count == 0) { return true ; } foreach ( var i in R) { int one = i.first; int two = i.second; if (one != two) { // Not a aRa tuple if (R.Contains( new pair(two, one))) { // If bRa tuple does exists in // relation R return false ; } } } // bRa tuples does not exists for all aRb in // relation R return true ; } } static public void Main() { // 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, 3)); R.Add( new pair(3, 4)); Relation obj = new Relation(); // R is anti-symmetric if (obj.checkAntiSymmetric(R)) { Console.WriteLine( "Anti-Symmetric Relation" ); } else { Console.WriteLine( "Not a Anti-Symmetric Relation" ); } } } // This code is contributed by lokesh |
Javascript
class Relation { constructor() {} checkAntiSymmetric(R) { // Property 1 if (R.size === 0) { return true ; } for (const i of R) { if (i[1] !== i[0]) { // Not a aRa tuple // making a mirror tuple const temp = [i[1], i[0]]; if (R.has(temp)) { // If bRa tuple exists in relation R return false ; } } } // bRa 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, 1]); R.add([1, 2]); R.add([2, 3]); R.add([3, 4]); const obj = new Relation(); // R is anti-symmetric if (obj.checkAntiSymmetric(R)) { console.log( "Anti-Symmetric Relation" ); } else { console.log( "Not a Anti-Symmetric Relation" ); } } main(); // This code is contributed by akashish__. |
Anti-Symmetric Relation
Time Complexity: O(N * log N) where N is the number of elements in the relation
Auxiliary Space: O(1)
Anti-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