Skip to main content

Find all distinct symmetric pairs in an array efficiently

Given an array of pairs, each pairs two integer elements. Find the all distinct pairs in this array which is symmetric to each others. For example.

Example 1
Given pairs
{(1,2)
(2,3)
(2,1)
(2,4)
(4,2)}
Output
(1,2)
(2,4)
Because
[
	(1, 2)
	 ↗↙↘↖  symmetric pair
	(2, 1)	

	(2, 4)
	 ↗↙↘↖  symmetric pair
	(4, 2)	

]

Example 2:
Given pairs
{
(1,1)
(1,1)
(4,1)
(2,4)
(4,2)
}
Output
(2,4)
Because
[
	(1, 1)
	 ↗↙↘↖  Equal pair
	(1, 1)	
	(Pair is repeating) 
	
	
	(2, 4)
	 ↗↙↘↖  Symmetric pair
	(4, 2)	

]

Here given code implementation process.

/*
    Java Program
    Find all distinct symmetric pairs in an array efficiently
*/
import java.util.HashMap;
import java.util.HashSet;
public class DistinctPairs
{
	// Find all the symmetric distinct pairs
	public void symmetricPairs(int[][] arr, int n)
	{
		// Result indicator
		boolean result = false;
		//  Collecting unique pair
		HashMap < Integer, HashSet < Integer > > pairs =
          new HashMap < Integer, HashSet < Integer > > ();
		// Get the distinct pair combination
		for (int i = 0; i < n; ++i)
		{
			if (pairs.containsKey(arr[i][0]))
			{
				// Add new value
				pairs.get(arr[i][0]).add(arr[i][1]);
			}
			else
			{
				// Add new key
				pairs.put(arr[i][0], new HashSet < Integer > ());
				// Add first value
				pairs.get(arr[i][0]).add(arr[i][1]);
			}
		}
		// Find symmetric pairs
		for (int key: pairs.keySet())
		{
			// iterate the pair element
			for (int value: pairs.get(key))
			{
				if (value != key && pairs.containsKey(value) 
                    && pairs.get(value).contains(key))
				{
					// print pair
					System.out.print("\n (" + key + "," + value + ")");
					pairs.get(value).remove(key);
					// Change result status
					result = true;
				}
			}
		}
		if (result == false)
		{
			// When no resultant pair exists
			System.out.print(" None \n");
		}
	}
	public static void main(String[] arg)
	{
		DistinctPairs task = new DistinctPairs();
        // Define pairs
        int [][]arr = 
        {
            {1,4},
            {2,4},
            {1,5},
            {4,2},
            {9,2},
            {2,6},
            {4,1},
            {8,8},
            {2,9},
            {1,5},
        };
		int n = arr.length;
		// Test case
		task.symmetricPairs(arr, n);
	}
}

Output

 (1,4)
 (2,4)
 (2,9)
// Include header file
#include <iostream>
#include <unordered_map>
#include <set>

using namespace std;
class DistinctPairs
{
    public:
        // Find all the symmetric distinct pairs
        void symmetricPairs(int arr[][2], int n)
        {
            // Result indicator
            bool result = false;
            //  Collecting unique pair
            unordered_map < int, set < int > > pairs;
            set < int > ::iterator value;
            // Get the distinct pair combination
            for (int i = 0; i < n; ++i)
            {
                if (pairs.find(arr[i][0]) != pairs.end())
                {
                    // Add new value
                    pairs[arr[i][0]].insert(arr[i][1]);
                }
                else
                {
                    // Add first value
                    pairs[arr[i][0]].insert(arr[i][1]);
                }
            }
            for (auto &it: pairs)
            {
                for (value = it.second.begin(); value != it.second.end(); ++value)
                {
                    if ( *value != it.first && pairs.find( *value) != pairs.end() 
                        && pairs[ *value].find(it.first) != pairs[ *value].end())
                    {
                        // print pair
                        cout << "\n (" << it.first << "," << *value << ")";
                        pairs[ *value].erase(it.first);
                        // Change result status
                        result = true;
                    }
                }
            }
            if (result == false)
            {
                // When no resultant pair exists
                cout << " None \n";
            }
        }
};
int main()
{
    DistinctPairs task = DistinctPairs();
    // Define pairs
    int arr[][2] = 
    {
        {1,4},
        {2,4},
        {1,5},
        {4,2},
        {9,2},
        {2,6},
        {4,1},
        {8,8},
        {2,9},
        {1,5}
    };
    int n = sizeof(arr) / sizeof(arr[0]);
    // Test case
    task.symmetricPairs(arr, n);
    return 0;
}

Output

 (1,4)
 (2,4)
 (2,9)
// Include namespace system
using System;
using System.Collections.Generic;
public class DistinctPairs
{
	// Find all the symmetric distinct pairs
	public void symmetricPairs(int[,] arr, int n)
	{
		// Result indicator
		Boolean result = false;
		//  Collecting unique pair
		Dictionary < int, HashSet <int> > pairs = 
          new Dictionary <int, HashSet <int>> ();
		// Get the distinct pair combination
		for (int i = 0; i < n; ++i)
		{
			if (pairs.ContainsKey(arr[i,0]))
			{
				// Add new value
				pairs[arr[i,0]].Add(arr[i,1]);
			}
			else
			{
				// Add new key
				pairs.Add(arr[i,0], new HashSet<int>());
				// Add first value
				pairs[arr[i,0]].Add(arr[i,1]);
			}
		}
		foreach(var entry in pairs)
		{
			foreach(int value in entry.Value)
			{
				if (value != entry.Key && pairs.ContainsKey(value) 
                    && pairs[value].Contains(entry.Key))
				{
					// print pair
					Console.Write("\n (" + entry.Key + "," + value + ")");
					pairs[value].Remove(entry.Key);
					// Change result status
					result = true;
				}
			}
		}
		if (result == false)
		{
			// When no resultant pair exists
			Console.Write(" None \n");
		}
	}
	public static void Main(String[] arg)
	{
		DistinctPairs task = new DistinctPairs();
		// Define pairs
		int[,] arr = {
			{
				1 , 4
			} , {
				2 , 4
			} , {
				1 , 5
			} , {
				4 , 2
			} , {
				9 , 2
			} , {
				2 , 6
			} , {
				4 , 1
			} , {
				8 , 8
			} , {
				2 , 9
			} , {
				1 , 5
			}  };
		int n = arr.GetLength(0);
		// Test case
		task.symmetricPairs(arr, n);
	}
}

Output

 (1,4)
 (2,4)
 (2,9)
<?php
/*
    Php Program
    Find all distinct symmetric pairs in an array efficiently
*/
class DistinctPairs
{
    // Find all the symmetric distinct pairs
    public  function symmetricPairs( & $arr, $n)
    {
        // Result indicator
        $result = false;
        //  Collecting unique pair
        $pairs = array();
        // Get the distinct pair combination
        for ($i = 0; $i < $n; ++$i)
        {
            if (array_key_exists($arr[$i][0], $pairs))
            {   
                if ((array_search($arr[$i][1], $pairs[$arr[$i][0]])) === false) 
                {
                    $pairs[$arr[$i][0]][] = ($arr[$i][1]);
                }
            }
            else
            {
                $pairs[$arr[$i][0]] = array();
                $pairs[$arr[$i][0]][] = ($arr[$i][1]);
            }
        }
        foreach($pairs as $key => $r)
        {
            foreach($pairs[$key] as $k => $value)
            {
                if ($value != $key && 
                    array_key_exists($value, $pairs) 
                    && in_array($key, $pairs[$value],True))
                {
                    // print pair
                    echo "\n (". $key .",". $value .")";
                    if (($d = array_search($key, $pairs[$value])) !== false) 
                    {
                        unset($pairs[$value][$d]);
                    }
                  
                
                    // Change result status
                    $result = true;
                }
            }
        }
        if ($result == false)
        {
            // When no resultant pair exists
            echo " None \n";
        }
    }
}

function main()
{
    $task = new DistinctPairs();
    // Define pairs
    $arr = array(
        array(1, 4), 
        array(2, 4), 
        array(1, 5), 
        array(4, 2), 
        array(9, 2), 
        array(2, 6), 
        array(4, 1), 
        array(8, 8), 
        array(2, 9), 
        array(1, 5)
    );
    $n = count($arr);
    // Test case
    $task->symmetricPairs($arr, $n);
}
main();

Output

 (1,4)
 (2,4)
 (2,9)
/*
    Node Js Program
    Find all distinct symmetric pairs in an array efficiently
*/
class DistinctPairs
{
	// Find all the symmetric distinct pairs
	symmetricPairs(arr, n)
	{
		// Result indicator
		var result = false;
		//  Collecting unique pair
		var pairs = new Map();
		// Get the distinct pair combination
		for (var i = 0; i < n; ++i)
		{
			if (pairs.has(arr[i][0]))
			{
				// Add new value
				pairs.get(arr[i][0]).add(arr[i][1]);
			}
			else
			{
				// Add new key
				pairs.set(arr[i][0], new Set());
				// Add first value
				pairs.get(arr[i][0]).add(arr[i][1]);
			}
		}
		for (let [key, record] of pairs)
		{
			for (let value of record.values())
			{
				if (value != key && pairs.has(value) && pairs.get(value).has(key))
				{
					// print pair
					process.stdout.write("\n (" + key + "," + value + ")");
					pairs.get(value).delete(key);
					// Change result status
					result = true;
				}
			}
		}
		if (result == false)
		{
			// When no resultant pair exists
			process.stdout.write(" None \n");
		}
	}
}

function main()
{
	var task = new DistinctPairs();
	// Define pairs
	var arr = [
		[1, 4] , 
        [2, 4] , 
        [1, 5] , 
        [4, 2] , 
        [9, 2] , 
        [2, 6] , 
        [4, 1] , 
        [8, 8] , 
        [2, 9] , 
        [1, 5]
	];
	var n = arr.length;
	// Test case
	task.symmetricPairs(arr, n);
}
main();

Output

 (1,4)
 (2,4)
 (2,9)
#  Python 3 Program
#  Find all distinct symmetric pairs in an array efficiently

class DistinctPairs :
	#  Find all the symmetric distinct pairs
	def symmetricPairs(self, arr, n) :
		#  Result indicator
		result = False
		#   Collecting unique pair
		pairs = dict()
		i = 0
		#  Get the distinct pair combination
		while (i < n) :
			if (arr[i][0] in pairs.keys()) :
				#  Add new value
				pairs.get(arr[i][0]).add(arr[i][1])
			else :
				#  Add new key
				pairs[arr[i][0]] = set()
				#  Add first value
				pairs.get(arr[i][0]).add(arr[i][1])
			
			i += 1
		
		for key, record in pairs.items() :
			for value in record :
				if (value != key and value in pairs.keys() 
                  and key in pairs.get(value)) :
					#  print pair
					print("\n (", key ,",", value ,")", end = "")
					pairs.get(value).remove(key)
					#  Change result status
					result = True
				
			
		
		if (result == False) :
			#  When no resultant pair exists
			print(" None ")
		
	

def main() :
	task = DistinctPairs()
	#  Define pairs
	arr = [
		[1, 4] , 
        [2, 4] , 
        [1, 5] , 
        [4, 2] , 
        [9, 2] , 
        [2, 6] , 
        [4, 1] , 
        [8, 8] , 
        [2, 9] , 
        [1, 5]
	]
	n = len(arr)
	#  Test case
	task.symmetricPairs(arr, n)

if __name__ == "__main__": main()

Output

 ( 1 , 4 )
 ( 2 , 9 )
 ( 2 , 4 )
#  Ruby Program
#  Find all distinct symmetric pairs in an array efficiently

class DistinctPairs 
	#  Find all the symmetric distinct pairs
	def symmetricPairs(arr, n) 
		#  Result indicator
		result = false
		#   Collecting unique pair
		pairs = Hash.new
		i = 0
		#  Get the distinct pair combination
		while (i < n) 
			if (pairs.key?(arr[i][0])) 
				pairs[arr[i][0]].push(arr[i][1])
			else 
				pairs[arr[i][0]] = []
				pairs[arr[i][0]].push(arr[i][1])
			end

			i += 1
		end
		pairs.each{ 
          |key,record| 
				for value in record do 
					if (value != key && pairs.key?(value) && pairs[value].include?(key)) 
						#  print pair
						print("\n (", key ,",", value ,")")
						pairs[value].delete(key)
						#  Change result status
						result = true
					end
				end
        }

		if (result == false) 
			#  When no resultant pair exists
			print(" None \n")
		end
	end
end

def main() 
	task = DistinctPairs.new()
	#  Define pairs
	arr = [
		[1, 4] , 
        [2, 4] , 
        [1, 5] , 
        [4, 2] , 
        [9, 2] , 
        [2, 6] , 
        [4, 1] , 
        [8, 8] , 
        [2, 9] , 
        [1, 5]
	]
	n = arr.length
	#  Test case
	task.symmetricPairs(arr, n)
end

main()

Output

 (1,4)
 (2,4)
 (2,9)
import scala.collection.mutable._;
/*
    Scala Program
    Find all distinct symmetric pairs in an array efficiently
*/
class DistinctPairs
{
	// Find all the symmetric distinct pairs
	def symmetricPairs(arr: Array[Array[Int]], n: Int): Unit = {
		// Result indicator
		var result: Boolean = false;
		//  Collecting unique pair
		var pairs: Map[Int, Set[Int]] = Map();
		var i: Int = 0;
		// Get the distinct pair combination
		while (i < n)
		{
			if (pairs.contains(arr(i)(0)))
			{
				// Add new value
				pairs.get(arr(i)(0)).get.add(arr(i)(1));
			}
			else
			{
				// Add new key
				pairs.addOne(arr(i)(0), Set());
				// Add first value
				pairs.get(arr(i)(0)).get.add(arr(i)(1));
			}
			i += 1;
		}
		for((key,record) <- pairs)
		{
         
            for (value <- record) 
			{
				if (value != key && pairs.contains(value) 
                    && pairs.get(value).get.contains(key))
				{
					// print pair
					print("\n (" + key + "," + value + ")");
					pairs.get(value).get.remove(key);
					// Change result status
					result = true;
				}
			}
		}
		if (result == false)
		{
			// When no resultant pair exists
			print(" None \n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: DistinctPairs = new DistinctPairs();
		// Define pairs
		var arr: Array[Array[Int]] = Array(
          Array(1, 4), 
          Array(2, 4), 
          Array(1, 5), 
          Array(4, 2), 
          Array(9, 2), 
          Array(2, 6), 
          Array(4, 1), 
          Array(8, 8), 
          Array(2, 9), 
          Array(1, 5)
        );
		var n: Int = arr.length;
		// Test case
		task.symmetricPairs(arr, n);
	}
}

Output

 (1,4)
 (2,4)
 (2,9)
import Foundation
/*
    Swift 4 Program
    Find all distinct symmetric pairs in an array efficiently
*/
class DistinctPairs
{
	// Find all the symmetric distinct pairs
	func symmetricPairs(_ arr: [
		[Int]
	], _ n: Int)
	{
		// Result indicator
		var result: Bool = false;
		//  Collecting unique pair
		var pairs = [Int: Set <Int> ]();
		var i: Int = 0;
		// Get the distinct pair combination
		while (i < n)
		{
			if (pairs.keys.contains(arr[i][0]))
			{
				// Add new value
				pairs[arr[i][0]]!.insert(arr[i][1]);
			}
			else
			{
				// Add new key
				pairs[arr[i][0]] = Set <Int> ();
				// Add first value
				pairs[arr[i][0]]!.insert(arr[i][1]);
			}
			i += 1;
		}
      	
		for (key, _) in pairs
		{
			for value in pairs[key]!
			{
				if (value  != key && pairs.keys.contains(value)
                    && pairs[value]!.contains(key))
				{
					// print pair
					print("\n (", key, ",", value, ")", terminator: "");
					pairs[value]!.remove(key);
					// Change result status
					result = true;
				}
			}
		}
		if (result == false)
		{
			// When no resultant pair exists
			print(" None ");
		}
	}
}
func main()
{
	let task: DistinctPairs = DistinctPairs();
	// Define pairs
	let arr: [[Int]] = [
		[1, 4] , 
        [2, 4] , 
        [1, 5] , 
        [4, 2] , 
        [9, 2] , 
        [2, 6] , 
        [4, 1] , 
        [8, 8] , 
        [2, 9] , 
        [1, 5]
	];
	let n: Int = arr.count;
	// Test case
	task.symmetricPairs(arr, n);
}
main();

Output

 ( 2 , 4 )
 ( 2 , 9 )
 ( 4 , 1 )
/*
    Kotlin Program
    Find all distinct symmetric pairs in an array efficiently
*/
class DistinctPairs
{
	// Find all the symmetric distinct pairs
	fun symmetricPairs(arr: Array < Array < Int >> , n: Int): Unit
	{
		// Result indicator
		var result: Boolean = false;
		//  Collecting unique pair
		var pairs = mutableMapOf<Int, MutableSet <Int>>();
		var i: Int = 0;
		// Get the distinct pair combination
		while (i < n)
		{
			if (pairs.containsKey(arr[i][0]))
			{
				// Add new value
				pairs.getValue(arr[i][0]).add(arr[i][1]);
			}
			else
			{
				// Add new key
				pairs.put(arr[i][0], mutableSetOf <Int> ());
				// Add first value
				pairs.getValue(arr[i][0]).add(arr[i][1]);
			}
			i += 1;
		}
		// Find symmetric pairs
		for (key in pairs.keys)
		{
			// iterate the pair element
			for (value in pairs.getValue(key))
			{
				if (value != key && pairs.containsKey(value)
                    && pairs.getValue(value).contains(key))
				{
					// print pair
					print("\n (" + key + "," + value + ")");
					pairs.getValue(value).remove(key);
					// Change result status
					result = true;
				}
			}
		}
		if (result == false)
		{
			// When no resultant pair exists
			print(" None \n");
		}
	}
}
fun main(args: Array <String> ): Unit
{
	var task: DistinctPairs = DistinctPairs();
	// Define pairs
	var arr: Array < Array <Int>> = arrayOf(
      arrayOf(1, 4), 
      arrayOf(2, 4), 
      arrayOf(1, 5), 
      arrayOf(4, 2), 
      arrayOf(9, 2), 
      arrayOf(2, 6), 
      arrayOf(4, 1), 
      arrayOf(8, 8), 
      arrayOf(2, 9), 
      arrayOf(1, 5)
    );
	var n: Int = arr.count();
	// Test case
	task.symmetricPairs(arr, n);
}

Output

 (1,4)
 (2,4)
 (2,9)
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment