Given N number of sets. The task is to write a program to perform a cartesian product of all the sets in a given order.
Example:
Input: 1st set: 1 2 2nd set: A 3rd set: x 4th set: 5 6 Output: [['1', 'A', 'x', '5'], ['1', 'A', 'x', '6'], ['2', 'A', 'x', '5'], ['2', 'A', 'x', '6']] Input: 1st set: 1 2 2nd set: A 3rd set: x y z Output: [['1', 'A', 'x'], ['1', 'A', 'y'], ['1', 'A', 'z'], ['2', 'A', 'x'], ['2', 'A', 'y'], ['2', 'A', 'z']]
Approach: The approach is to compute the product of set-1 and set-2 at the beginning and then the resultant of set-1 and set-2 will have a product with set-3 and then the resultant of set-1, set-2, and set-3 will have a Cartesian product with set-4 and so on till set-n.
Below is the implementation of the above approach.
Python3
# Python program for cartesian # product of N-sets # function to find cartesian product of two sets def cartesianProduct(set_a, set_b): result =[] for i in range(0, len(set_a)): for j in range(0, len(set_b)): # for handling case having cartesian # product first time of two sets if type(set_a[i]) != list: set_a[i] = [set_a[i]] # copying all the members # of set_a to temp temp = [num for num in set_a[i]] # add member of set_b to # temp to have cartesian product temp.append(set_b[j]) result.append(temp) return result # Function to do a cartesian # product of N sets def Cartesian(list_a, n): # result of cartesian product # of all the sets taken two at a time temp = list_a[0] # do product of N sets for i in range(1, n): temp = cartesianProduct(temp, list_a[i]) print(temp) # Driver Code list_a = [[1, 2], # set-1 ['A'], # set-2 ['x', 'y', 'z']] # set-3 # number of sets n = len(list_a) # Function is called to perform # the cartesian product on list_a of size n Cartesian(list_a, n) |
Output:
[[1, 'A', 'x'], [1, 'A', 'y'], [1, 'A', 'z'], [2, 'A', 'x'], [2, 'A', 'y'], [2, 'A', 'z']]
Time Complexity: O(n3)
Auxiliary Space: O(n*m), Here n is the number of sets and m is the maximum element in a set. The extra space is used to store the result.
