Python – Most common Combination in Matrix

0 0 3 minutes read

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 modules
from collections import Counter
from itertools import combinations
 
# initializing list
test_list = [[4, 5, 6, 2], [7, 6, 3, 2],
             [4, 2, 6, 7], [1, 2, 4, 6]]
 
# printing original list
print("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 combinations
res = [cmb for cmb, 
       cnt in res.items() if cnt == res.most_common(1)[0][1]]
 
# printing result
print("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 list
test_list = [[4, 5, 6, 2], [7, 6, 3, 2],
             [4, 2, 6, 7], [1, 2, 4, 6]]
 
# printing original list
print("The original list is : " + str(test_list))
 
# initialize dictionary to keep track of combination frequencies
comb_count = {}
 
# loop through each sublist in the input list
for 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 dictionary
max_freq = 0
most_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.