Given Tuple list, compute bidirectional tuples.
Input : test_list = [(5, 6), (1, 2), (6, 5), (9, 1), (6, 5), (2, 1)]
Output : 3
Explanation : (1, 2), (2, 1); (5, 6) -> [(6, 5), (6, 5)], total 3 pairs.Input : test_list = [(5, 6), (1, 3), (6, 5), (9, 1), (6, 5), (2, 1)]
Output : 2
Explanation : (5, 6) -> [(6, 5), (6, 5)], total 2 pairs.
Method 1: Using loop
In this we check for each element if we have any other element which is bidirectional, Once the pair is found, counter is incremented.
Python3
# Python3 code to demonstrate working of# Count Bidirectional Tuple Pairs# Using loop# initializing listtest_list = [(5, 6), (1, 2), (6, 5), (9, 1), (6, 5), (2, 1)]# printing original listprint("The original list is : " + str(test_list))res = 0for idx in range(0, len(test_list)): for iidx in range(idx + 1, len(test_list)): # checking bidirection if test_list[iidx][0] == test_list[idx][1] and test_list[iidx][1] == test_list[idx][0]: res += 1# printing resultprint("Bidirectional pairs count : " + str(res)) |
The original list is : [(5, 6), (1, 2), (6, 5), (9, 1), (6, 5), (2, 1)] Bidirectional pairs count : 3
Time Complexity: O(n*n)
Auxiliary Space: O(n)
Method 2: Using a dictionary
Step-by-step approach:
- Initialize an empty dictionary to store the frequency of each tuple.
- Populate the dictionary with the frequency of each tuple using a loop.
- Count the bidirectional pairs by iterating over the dictionary. For each tuple in the dictionary, we check if its reverse tuple is also in the dictionary. If it is, we add the product of their frequencies to the result.
- Divide the result by 2 to account for bidirectional pairs being counted twice.
- Print the final result.
Python3
# initializing listtest_list = [(5, 6), (1, 2), (6, 5), (9, 1), (6, 5), (2, 1)]# initializing an empty dictionaryfreq_dict = {}# populating the dictionary with frequency of each tuplefor tup in test_list: freq_dict[tup] = freq_dict.get(tup, 0) + 1# counting the bidirectional pairsres = 0for tup, freq in freq_dict.items(): reverse_tup = (tup[1], tup[0]) if reverse_tup in freq_dict: res += freq * freq_dict[reverse_tup]# dividing by 2 to account for bidirectional pairs counted twiceres //= 2# printing resultprint("Bidirectional pairs count : " + str(res)) |
Bidirectional pairs count : 3
Time complexity: O(n), where n is the length of the input list.
Auxiliary space: O(n) to store the dictionary.
Method 3 : uses the built-in Counter class from the collections module
step-by-step approach
- Import the Counter class from the collections module.
- Initialize a list of tuples called “test_list”. This list contains the tuples for which we want to find the bidirectional pairs.
- Create a Counter object by passing the “test_list” as an argument to the Counter() function. The Counter object will count the frequency of each tuple in the “test_list”.
- Initialize a variable called “res” to 0. This variable will store the count of bidirectional pairs.
- Use a for loop to iterate over the tuples and their frequencies in the Counter object.
- Inside the for loop, create a tuple called “reverse_tup” by reversing the current tuple using the reversed() function and passing it to the tuple() constructor.
- Check if the “reverse_tup” exists in the Counter object.
- If “reverse_tup” exists in the Counter object, add the product of the frequency of the current tuple and the frequency of the reverse tuple to the “res” variable.
- After the for loop, divide the “res” variable by 2 to account for bidirectional pairs counted twice.
- Print the final count of bidirectional pairs.
Python3
from collections import Counter# initializing listtest_list = [(5, 6), (1, 2), (6, 5), (9, 1), (6, 5), (2, 1)]# counting the frequency of each tuplecounter = Counter(test_list)# counting the bidirectional pairsres = 0for tup, freq in counter.items(): reverse_tup = tuple(reversed(tup)) if reverse_tup in counter: res += freq * counter[reverse_tup]# dividing by 2 to account for bidirectional pairs counted twiceres //= 2# printing resultprint("Bidirectional pairs count: " + str(res)) |
Bidirectional pairs count: 3
The time complexity of this solution is O(n), since we only need to loop over the list once and do constant-time lookups in the Counter.
The space complexity is also O(n), since we need to store the frequency of each tuple in the Counter.
