Cartesian Product

The cartesian product of two sets A and B, denoted A x B, is the set of all ordered pairs (a, b) where a belongs to A and b belongs to B.

It is the set of all possible combinations of elements from the two sets.

For example:

If A = {1, 2}, B = {3, 4}

Then, A x B = {(1, 3), (1, 4), (2, 3), (2, 4)}

The cartesian product is useful for generating all possible permutations and combinations from given sets systematically.

Solution

Here is how cartesian product can be implemented:

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
List<int[]> cartesianProduct(int[] A, int[] B) {
  List<int[]> result = new ArrayList<>();

  for (int a : A) {
    for (int b : B) {
      result.add(new int[]{a, b}); 
    }
  }

  return result;
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
vector<vector<int>> cartesianProduct(vector<int> A, vector<int> B) {
  vector<vector<int>> result;

  for (int a : A) {
    for (int b : B) {
      result.push_back({a, b});
    }
  }

  return result;
} 

Python

1
2
3
4
5
6
7
8
def cartesian_product(A, B):
  
  result = []
  for a in A:
    for b in B:
      result.append([a, b])

  return result

We generate the combinations by looping over both sets and pairing elements.

The cartesian product provides an easy way to systematically generate all combinations.

Description: Cartesian Product

The Cartesian Product is a mathematical operation that takes multiple sets and returns a new set containing all possible ordered pairs (or triples, or more) of elements from those sets. In the context of programming and computer science, it’s often used to generate all possible combinations of elements from two or more arrays or lists.

Solution:

Below are implementations to find the Cartesian Product of two sets in Java, C++, and Python.

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static List<List<Integer>> cartesianProduct(List<Integer> setA, List<Integer> setB) {
        List<List<Integer>> result = new ArrayList<>();

        for (int a : setA) {
            for (int b : setB) {
                List<Integer> pair = new ArrayList<>();
                pair.add(a);
                pair.add(b);
                result.add(pair);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        List<Integer> setA = List.of(1, 2, 3);
        List<Integer> setB = List.of(4, 5);

        List<List<Integer>> result = cartesianProduct(setA, setB);
        System.out.println("Cartesian Product: " + result);
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>

std::vector<std::pair<int, int>> cartesianProduct(const std::vector<int>& setA, const std::vector<int>& setB) {
    std::vector<std::pair<int, int>> result;
    
    for (const int& a : setA) {
        for (const int& b : setB) {
            result.push_back(std::make_pair(a, b));
        }
    }

    return result;
}

int main() {
    std::vector<int> setA = {1, 2, 3};
    std::vector<int> setB = {4, 5};
    
    std::vector<std::pair<int, int>> result = cartesianProduct(setA, setB);
    
    std::cout << "Cartesian Product: ";
    for (const auto& pair : result) {
        std::cout << "(" << pair.first << ", " << pair.second << ") ";
    }
    
    return 0;
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
from itertools import product

def cartesian_product(set_a, set_b):
    return [(a, b) for a in set_a for b in set_b]

if __name__ == "__main__":
    set_a = [1, 2, 3]
    set_b = [4, 5]
    
    result = cartesian_product(set_a, set_b)
    print(f"Cartesian Product: {result}")

Key Takeaways

The Cartesian Product is a way to generate all possible combinations from multiple sets.
The operation is widely used in various domains like databases, mathematics, and algorithms.
The sample code demonstrates how you can find the Cartesian Product of two sets in Java, C++, and Python.