Python – Group Records on Similar index elements

Sometimes, while working with Python records, we can have a problem in which we need to perform grouping of particular index of tuple, on basis of similarity of rest of indices. This type of problems can have possible applications in Web development domain. Let’s discuss certain ways in which this task can be performed.

Input : test_list = [(4, 5, 10), (4, 5, 7), (4, 5, 12)] 
Output : ((4, 5, [10, 7, 12]), ) 

Input : test_list = [(4, 5, 10)] 
Output : [(4, 5, [10])]

Method #1 : Using defaultdict() + loop 

The combination of above functions offer a brute approach to solve this problem. In this, we group elements and club into one using defaultdict() on basis of equality of rest of elements.

The original list is : [(4, 7, 13), (4, 5, 7), (6, 7, 10), (4, 5, 15), (6, 7, 12)]
Tuples after grouping : ((4, 7, [13]), (4, 5, [7, 15]), (6, 7, [10, 12]))

Time Complexity: O(n*n) where n is the number of elements in the list “test_list”.  defaultdict() + loop performs n*n number of operations.
Auxiliary Space: O(n), extra space is required where n is the number of elements in the list

Method #2 : Using groupby() + generator expression 

The combinations of above functions can be used to solve this problem. In this, we perform the grouping of all elements using groupby() and generation of tuple list using generator expression. Needs sorted list for this method. 

The original list is : [(4, 7, 13), (4, 5, 7), (6, 7, 10), (4, 5, 15), (6, 7, 12)]
Tuples after grouping : ((4, 7, [13]), (4, 5, [7, 15]), (6, 7, [10, 12]))

Method 3: Using dictionary comprehension and setdefault()

1. Initialize an empty dictionary temp to hold our grouped records.
2. Loop through the elements of test_list. For each tuple (a, b, c), we check if the key (a, b) exists in the dictionary temp. If it does, we append c to the value list associated with the key. If it doesn’t, we create a new key (a, b) and assign a new list containing c as its value.
3. Use dictionary comprehension to create a list of tuples res. For each key-value pair in temp.items(), we extract the first and second elements of the key and the value list, and create a new tuple with these elements.
4. Print the resulting list of tuples.

The original list is : [(4, 7, 13), (4, 5, 7), (6, 7, 10), (4, 5, 15), (6, 7, 12)]
Tuples after grouping : [(4, 5, [7, 15]), (4, 7, [13]), (6, 7, [10, 12])]

Time complexity: O(n), where n is the length of test_list. We loop through the list once, and each dictionary operation (checking for a key and appending a value) takes constant time.

Auxiliary space: O(m), where m is the number of distinct key tuples in test_list. We store a dictionary with at most m key-value pairs, and a list of at most n elements in the worst case.

Method #4: Using itertools.groupby() + lambda function

Approach:

1. Import the itertools module.
2. Sort the list by the first two elements of each tuple.
3. Use itertools.groupby() function to group the tuples by the first two elements.
4. Use a lambda function to extract the third element from each grouped tuple.
5. Create a list of tuples, where the first two elements are the key and the third element is a list of values.

Below is the implementation of the above approach:

The original list is : [(4, 7, 13), (4, 5, 7), (6, 7, 10), (4, 5, 15), (6, 7, 12)]
Tuples after grouping : [(4, 5, [7, 15]), (4, 7, [13]), (6, 7, [10, 12])]

Time complexity: O(n log n) (due to the sorting operation)
Auxiliary space: O(n) (to store the result list)

Method #5: Using defaultdict() + list comprehension

The original list is : [(4, 7, 13), (4, 5, 7), (6, 7, 10), (4, 5, 15), (6, 7, 12)]
Tuples after grouping : [(4, 7, [13]), (4, 5, [7, 15]), (6, 7, [10, 12])]

Time complexity: O(n) since it requires a single pass through the input list. 
Auxiliary space: O(n) since it uses a dictionary to store the groups.