Sometimes, while working with data, we need to create data as all possible pairs of containers. This type of application comes from the web development domain. Let’s discuss certain ways in which this task can be performed.
Using list comprehension
list comprehension in Python is a one-liner way to perform this particular task. In this, we just shorten the task of looping in one line to generate all possible pairs of tuples with list elements.
Python3
# Python3 code to demonstrate working of# Construct Cartesian Product Tuple list# using list comprehension# initialize list and tupletest_list = [1, 4, 6, 7]test_tup = (1, 3)# printing original list and tupleprint("The original list : " + str(test_list))print("The original tuple : " + str(test_tup))# Construct Cartesian Product Tuple list# using list comprehensionres = [(a, b) for a in test_tup for b in test_list]# printing resultprint("The Cartesian Product is : " + str(res)) |
Output
The original list : [1, 4, 6, 7] The original tuple : (1, 3) The Cartesian Product is : [(1, 1), (1, 4), (1, 6), (1, 7), (3, 1), (3, 4), (3, 6), (3, 7)]
Using itertools.product()
This task can also be performed using a single function that internally performs the task of returning the required Cartesian Product, here we are using itertools.product():
Python3
# using itertools.product()from itertools import product# initialize list and tupletest_list = [1, 4, 6, 7]test_tup = (1, 3)# printing original list and tupleprint("The original list : " + str(test_list))print("The original tuple : " + str(test_tup))# Construct Cartesian Product Tuple list# using itertools.product()res = list(product(test_tup, test_list))# printing resultprint("The Cartesian Product is : " + str(res)) |
Output
The original list : [1, 4, 6, 7] The original tuple : (1, 3) The Cartesian Product is : [(1, 1), (1, 4), (1, 6), (1, 7), (3, 1), (3, 4), (3, 6), (3, 7)]
Using recursion
Here we are not using any built-in library rather we are using the concept of recursion.
Python3
def product(ar_list): if not ar_list: yield () else: for a in ar_list[0]: for prod in product(ar_list[1:]): yield (a,)+prod# driver codetest_list = [1, 4, 6, 7]test_tup = (1, 3)# printing original list and tupleprint("The original list : " + str(test_list))print("The original tuple : " + str(test_tup))res=list(product([test_tup,test_list]))# printing the resultprint("The Cartesian Product is : " + str(res)) |
Output
The original list : [1, 4, 6, 7] The original tuple : (1, 3) The Cartesian Product is : [(1, 1), (1, 4), (1, 6), (1, 7), (3, 1), (3, 4), (3, 6), (3, 7)]
Using map() and lambda function
Step-by-step approach:
- Initialize the list and tuple.
- Using the lambda function and map(), create a list of tuples by iterating through the elements of the test_list and combining them with the first element of test_tup.
- Using the lambda function and map(), create another list of tuples by iterating through the elements of the test_list and combining them with the second element of test_tup.
- Concatenate the two lists created in the above two steps to get the Cartesian product.
- Print the Cartesian product.
Below is the implementation of the above approach:
Python3
#initialize list and tupletest_list = [1, 4, 6, 7]test_tup = (1, 3)#printing original list and tupleprint("The original list : " + str(test_list))print("The original tuple : " + str(test_tup))#Construct Cartesian Product Tuple list#using map() and lambda functionres = list(map(lambda x: (test_tup[0], x), test_list)) + list(map(lambda x: (test_tup[1], x), test_list))#printing resultprint("The Cartesian Product is : " + str(res)) |
Output
The original list : [1, 4, 6, 7] The original tuple : (1, 3) The Cartesian Product is : [(1, 1), (1, 4), (1, 6), (1, 7), (3, 1), (3, 4), (3, 6), (3, 7)]
Time complexity: O(n), where n is the length of the input list
Space complexity: O(n), where n is the length of the input list
Using numpy:
Algorithm:
- Convert the input list test_list to a NumPy array arr[].
- Use the mesh grid function to get the Cartesian product of the elements of the tuple test_tup and the array arr.
- This returns two arrays X and Y that represent the coordinates of the points in a grid.
- Stack the arrays X and Y vertically using the column_stack function to get the desired output res.
Below is the implementation of the above approach:
Python3
import numpy as nptest_list = [1, 4, 6, 7]test_tup = (1, 3)# Print original list and tupleprint("The original list : " + str(test_list))print("The original tuple : " + str(test_tup))# Convert list to numpy arrayarr = np.array(test_list)# Get Cartesian product using meshgrid functionX, Y = np.meshgrid([test_tup[0], test_tup[1]], arr)res = np.column_stack((X.ravel(), Y.ravel()))# Print resultprint("The Cartesian Product is : " + str(res))# This code is contributed by Jyothi pinjala |
Output:
The original list : [1, 4, 6, 7] The original tuple : (1, 3) The Cartesian Product is : [[1 1] [3 1] [1 4] [3 4] [1 6] [3 6] [1 7] [3 7]]
Time Complexity: O(N2), where n is the length of the input list test_list.
Space Complexity: O(N2)
Using list comprehension and tuple concatenation:
- Initializes a list test_list and a tuple test_tup.
- The original list and tuple are printed using print() statements.
- Cartesian product tuple list is constructed using list comprehension and tuple concatenation We are just iterating
- The result is printed using a print() statement.
Python3
# initialize list and tupletest_list = [1, 4, 6, 7]test_tup = (1, 3)# printing original list and tupleprint("The original list : " + str(test_list))print("The original tuple : " + str(test_tup))# Construct Cartesian Product Tuple list using list comprehension and tuple concatenationres = [(a, ) + (b, ) for a in test_tup for b in test_list]# printing resultprint("The Cartesian Product is : " + str(res)) |
Output
The original list : [1, 4, 6, 7] The original tuple : (1, 3) The Cartesian Product is : [(1, 1), (1, 4), (1, 6), (1, 7), (3, 1), (3, 4), (3, 6), (3, 7)]
Time complexity: O(n), where n is the length of the input list
Space complexity: O(n), where n is the length of the input list
