Given a list of tuples, the task is to print another list containing tuple of same first element. Below are some ways to achieve above tasks.
Example:
Input : [('x', 'y'), ('x', 'z'), ('w', 't')]
Output: [('w', 't'), ('x', 'y', 'z')]
Method #1: Using extend
Python3
# Python code to find common# first element in list of tuple# Function to solve the taskdef find(Input): out = {} for elem in Input: try: out[elem[0]].extend(elem[1:]) except KeyError: out[elem[0]] = list(elem) return [tuple(values) for values in out.values()]# List initializationInput = [('x', 'y'), ('x', 'z'), ('w', 't')]# Calling functionOutput = (find(Input))# Printingprint("Initial list of tuple is :", Input)print("List showing common first element", Output) |
Initial list of tuple is : [('x', 'y'), ('x', 'z'), ('w', 't')]
List showing common first element [('w', 't'), ('x', 'y', 'z')]
Time Complexity: O(n), where n is the number of tuples in the input list.
Auxiliary Space: O(n), as the output dictionary requires a space of O(n) to store the elements.
Method #2: Using defaultdict
Python3
# Python code to find common first# element in list of tuple# Importingfrom collections import defaultdict# Function to solve the taskdef find(pairs): mapp = defaultdict(list) for x, y in pairs: mapp[x].append(y) return [(x, *y) for x, y in mapp.items()]# Input list initializationInput = [('p', 'q'), ('p', 'r'), ('p', 's'), ('m', 't')]# calling functionOutput = find(Input)# Printingprint("Initial list of tuple is :", Input)print("List showing common first element", Output) |
Initial list of tuple is : [('p', 'q'), ('p', 'r'), ('p', 's'), ('m', 't')]
List showing common first element [('m', 't'), ('p', 'q', 'r', 's')]
Time complexity: O(n), where n is the number of tuples in the input list.
Auxiliary space: O(n), where n is the number of tuples in the input list.
Method #3: Using for loop
Python3
# Python code to find common# first element in list of tuple# List initializationInput = [('x', 'y'), ('x', 'z'), ('w', 't')]Output = []v = []for i in Input: if i[0] not in v: v.append(i[0])for i in v: p = [] p.append(i) for j in Input: if j[0] == i: p.append(j[1]) p = tuple(p) Output.append(p)# Printingprint("Initial list of tuple is :", Input)print("List showing common first element", Output) |
Initial list of tuple is : [('x', 'y'), ('x', 'z'), ('w', 't')]
List showing common first element [('x', 'y', 'z'), ('w', 't')]
Time complexity: O(n^2) where n is the length of Input list. The nested loop iterates over the Input list.
Auxiliary space: O(n) where n is the length of Input list.
Method #4: Using groupby
The function find takes in a list of tuples as input and returns a new list of tuples where each tuple contains the first element of each tuple in the input list and all the second elements with the same first element.
First, the input list is sorted by the first element of each tuple using the sorted function and a lambda function as the key. This is done to ensure that all tuples with the same first element are together.
Then, the itertools.groupby function is used to group the tuples in the sorted list by the first element. The groupby function returns an iterator that returns the key and a group of tuples with the same key. The returned iterator is passed to the list function to create a list of lists, where each inner list contains the tuples with the same first element.
Finally, a list comprehension is used to create a new list of tuples, where the first element is the key and the rest are the values. The key is taken from the first tuple in each inner list, and the values are taken from the second element of each tuple in the inner list. The resulting list of tuples is returned by the function.
Python3
import itertoolsdef find(input_list): # Sort the input list by the first element of each tuple sorted_list = sorted(input_list, key=lambda x: x[0]) # Group the tuples by the first element using itertools.groupby grouped_list = [list(group) for key, group in itertools.groupby(sorted_list, lambda x: x[0])] # Create a new list of tuples, where the first element is the key and the rest are the values return [tuple([group[0][0]] + [item[1] for item in group]) for group in grouped_list]Input = [('x', 'y'), ('x', 'z'), ('w', 't')]Output = find(Input)print(Output)#This code is contributed by Edula Vinay Kumar Reddy |
[('w', 't'), ('x', 'y', 'z')]
Time complexity: O(n * log(n)) due to the sorting step
Auxiliary Space: O(n) to store the sorted list and grouped list
Method #5: Using set intersection and list comprehension
Use set intersection to find the common first element in the list of tuples.
Step-by-step approach:
- Create a set of the first elements of each tuple using a list comprehension and set() function.
- Create a list of tuples by iterating through the set and for each first element, create a list of tuples containing that element and any other elements from the original list of tuples that have the same first element.
- Return the list of tuples containing the common first element and any other elements.
Below is the implementation of the above approach:
Python3
def find(Input): first_elems = set([t[0] for t in Input]) common_elems = [] for elem in first_elems: sub_list = [t for t in Input if t[0] == elem] common_elem = tuple([elem] + [x for t in sub_list for x in t[1:]]) common_elems.append(common_elem) return common_elems# List initializationInput = [('x', 'y'), ('x', 'z'), ('w', 't')]# Calling functionOutput = find(Input)# Printingprint("Initial list of tuple is :", Input)print("List showing common first element", Output) |
Initial list of tuple is : [('x', 'y'), ('x', 'z'), ('w', 't')]
List showing common first element [('w', 't'), ('x', 'y', 'z')]
Time complexity: O(n^2), where n is the length of the input list.
Auxiliary space: O(n), where n is the length of the input list.
Method #6: Using reduce():
Algorithm:
Sort the input list by the first element of each tuple.
Group the tuples by the first element using reduce() and a dictionary.
Convert the dictionary to a list of tuples.
Python3
from functools import reducedef find(input_list): # Sort the input list by the first element of each tuple sorted_list = sorted(input_list, key=lambda x: x[0]) # Group the tuples by the first element using reduce() and a dictionary grouped_dict = reduce(lambda x, y: x.update({y[0]: x[y[0]] + [y[1]]}) or x if y[0] in x else x.update({y[0]: [y[1]]}) or x, sorted_list, {}) # Convert the dictionary to a list of tuples return [(k, *v) for k, v in grouped_dict.items()]Input = [('x', 'y'), ('x', 'z'), ('w', 't')]Output = find(Input)# Printingprint("Initial list of tuple is :", Input)print("List showing common first element", Output)#This code is contributed by Rayudu. |
Initial list of tuple is : [('x', 'y'), ('x', 'z'), ('w', 't')]
List showing common first element [('w', 't'), ('x', 'y', 'z')]
Time complexity: O(nlogn) for sorting the input list + O(n) for reducing the list to a dictionary + O(n) for converting the dictionary to a list of tuples, where n is the length of the input list. Therefore, the overall time complexity is O(nlogn).
Auxiliary Space: O(n) for the dictionary created in the reduce() function and O(n) for the list of tuples created in the return statement. Therefore, the overall space complexity is O(n).
