Given a matrix, the task is to write a python program to extract the most common occurrence of any combination of elements size greater than 2.
Examples:
Input: test_list = [[4, 5, 6, 2], [7, 6, 3, 2], [4, 2, 6, 7], [1, 2, 4, 6]] Output: [(2, 6)] Explanation: [2, 6] in combination occurs 4 times, maximum of all.
Input: test_list = [[4, 5, 6, 2], [7, 6, 3, 2], [4, 2, 6, 7], [1, 2, 4, 7]] Output: [(2, 4), (2, 6), (2, 7)] Explanation: [2, 6], [2, 4] and [2, 7] in combination occur 3 times each, maximum of all.
Approach: Using combinations() + Counter() + most_common() + list comprehension
In this, combinations are computed using combinations(), Counter(), and keeps track of frequencies of each combination. At last, most_common() is used to extract the maximum frequency of combinations that occurred.
Python3
# Python3 code to demonstrate working of# Most common Combination in Matrix# import required modulesfrom collections import Counterfrom itertools import combinations# initializing listtest_list = [[4, 5, 6, 2], [7, 6, 3, 2], [4, 2, 6, 7], [1, 2, 4, 6]]# printing original listprint("The original list is : " + str(test_list))res = Counter()for sub in test_list: # ignoring 1 sized substring if len(sub) < 2: continue # sorting for common ordering sub.sort() # getting and storing combinations for size in range(2, len(sub) + 1): for comb in combinations(sub, size): res[comb] += 1# getting most common combinationsres = [cmb for cmb, cnt in res.items() if cnt == res.most_common(1)[0][1]]# printing resultprint("The Most common combination : " + str(res)) |
Output:
The original list is : [[4, 5, 6, 2], [7, 6, 3, 2], [4, 2, 6, 7], [1, 2, 4, 6]] The Most common combination : [(2, 6)]
Time Complexity: O(nlogn+mlogm)
Auxiliary Space: O(k)
Approach: Using nested for loops and dictionaries
Steps:
- Define an input list of lists test_list that contains sublists of integers.
- Print the original list.
- Create an empty dictionary comb_count to keep track of the frequency of each combination.
- Loop through each sublist in the input list using a for loop.
- For each sublist, loop through each combination of 2 or more elements using nested for loops.
- Sort the combination in ascending order and convert it to a tuple to make it hashable.
- Check if the combination already exists in the comb_count dictionary. If it does, increment its frequency count. Otherwise, add it to the dictionary with a frequency count of 1.
- After all, sublists have been processed, the comb_count dictionary contains the frequency count of each combination.
- Find the most common combination(s) by looping through the dictionary using a for loop.
- Initialize a variable max_freq to 0 and a list most_common_comb to an empty list.
- For each key-value pair in the comb_count dictionary, check if its frequency count is greater than max_freq. If it is, update max_freq to the new maximum and reset most_common_comb to a list containing only the current combination. If it is equal to max_freq, append the current combination to most_common_comb.
- After all key-value pairs have been processed, the most_common_comb list contains the most common combination(s) with the highest frequency count.
- Print the most common combination(s).
Python3
# Python3 code to demonstrate working of# Most common Combination in Matrix# initializing listtest_list = [[4, 5, 6, 2], [7, 6, 3, 2], [4, 2, 6, 7], [1, 2, 4, 6]]# printing original listprint("The original list is : " + str(test_list))# initialize dictionary to keep track of combination frequenciescomb_count = {}# loop through each sublist in the input listfor sublist in test_list: # loop through each combination of 2 or # more elements in the sublist for i in range(len(sublist)): for j in range(i+1, len(sublist)): comb = tuple(sorted([sublist[i], sublist[j]])) if comb in comb_count: comb_count[comb] += 1 else: comb_count[comb] = 1# find the most common combination(s) by # looping through the dictionarymax_freq = 0most_common_comb = []for comb, freq in comb_count.items(): # Update frequency if it is greater than max frequency if freq > max_freq: max_freq = freq most_common_comb = [comb] # Else do not update elif freq == max_freq: most_common_comb.append(comb)# print the most common combination(s)print("The Most common combination : " + str(most_common_comb)) |
Output
The original list is : [[4, 5, 6, 2], [7, 6, 3, 2], [4, 2, 6, 7], [1, 2, 4, 6]] The Most common combination : [(2, 6)]
Time complexity: O(n^2) where n is the maximum length of any sublist in the input list since we need to loop through each pair of elements in each sublist.
Auxiliary space: O(n^2) to store the combinations and their frequency in the dictionary.
