Cartesian Product of Two Sets using C, C++, Java and Python

---

❮ Previous    Next ❯

---

---

Objective

To write a program in C, C++, Java and Python to create two sets and find their Cartesian Product.

---

Theory

Let A and B be two sets. The Cartesian Product of A and B is represented as:

A × B

It is defined as the set of all ordered pairs (a,b) such that a belongs to Set A and b belongs to Set B. Mathematically,

A × B = { (a,b) | a ? A and b ? B }

---

Example

Consider:

A = {1, 2}

B = {3, 4}

To find the Cartesian Product, combine every element of A with every element of B.

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

---

Understanding Ordered Pairs

An ordered pair is written in the form:

(a,b)

The order of the elements is important. For example:

(1,3) ? (3,1)

Therefore, the Cartesian Product A × B is generally different from B × A.

---

Example of B × A

For:

A = {1,2}

B = {3,4}

we have:

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

Clearly:

A × B ? B × A

---

Cardinality of Cartesian Product

If Set A contains n elements and Set B contains m elements, then the Cartesian Product contains:

|A × B| = |A| × |B|

Therefore, if:

|A| = 2

|B| = 3

then:

|A × B| = 2 × 3 = 6

---

Cartesian Product Example Table

Set A	Set B	Cartesian Product
{1,2}	{3,4}	{(1,3),(1,4),(2,3),(2,4)}

---

Algorithm

1. Start.
2. Read the number of elements in Set A.
3. Read the elements of Set A.
4. Read the number of elements in Set B.
5. Read the elements of Set B.
6. Take each element of Set A one by one.
7. For each element of A, take every element of Set B.
8. Create the ordered pair (A[i], B[j]).
9. Display the ordered pair.
10. Repeat until all combinations have been generated.
11. Stop.

---

Flowchart

---

Important Properties

• The Cartesian Product contains ordered pairs.
• The order of elements in an ordered pair is important.
• A × B is generally different from B × A.
• If A contains n elements and B contains m elements, A × B contains n × m elements.
• If either set is empty, the Cartesian Product is empty.

---

C Program

The following C program creates two sets and displays their Cartesian Product using nested loops.

/* C Program to Find Cartesian Product of Two Sets */

#include <stdio.h>

int main()
{
    int A[100], B[100];
    int n, m;
    int i, j;

    printf("Enter number of elements in Set A: ");
    scanf("%d", &n);

    printf("Enter elements of Set A:\n");

    for(i = 0; i < n; i++)
    {
        scanf("%d", &A[i]);
    }

    printf("Enter number of elements in Set B: ");
    scanf("%d", &m);

    printf("Enter elements of Set B:\n");

    for(i = 0; i < m; i++)
    {
        scanf("%d", &B[i]);
    }

    printf("\nCartesian Product A x B:\n");

    printf("{ ");

    for(i = 0; i < n; i++)
    {
        for(j = 0; j < m; j++)
        {
            printf("(%d,%d)", A[i], B[j]);

            if(i != n - 1 || j != m - 1)
            {
                printf(", ");
            }
        }
    }

    printf(" }\n");

    return 0;
}

---

Sample Output (C)

Enter number of elements in Set A: 2

Enter elements of Set A:
1 2

Enter number of elements in Set B: 2

Enter elements of Set B:
3 4

Cartesian Product A x B:
{ (1,3), (1,4), (2,3), (2,4) }

---

How the C Program Works

1. Two arrays are used to store Set A and Set B.
2. The program reads the elements of both sets.
3. The outer loop selects one element from Set A.
4. The inner loop selects every element from Set B.
5. An ordered pair is formed using the two selected elements.
6. The process continues until every possible pair has been generated.

---

C++ Program

/* C++ Program to Find Cartesian Product of Two Sets */

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, m;

    cout << "Enter number of elements in Set A: ";
    cin >> n;

    vector<int> A(n);

    cout << "Enter elements of Set A:\n";

    for(int i = 0; i < n; i++)
    {
        cin >> A[i];
    }

    cout << "Enter number of elements in Set B: ";
    cin >> m;

    vector<int> B(m);

    cout << "Enter elements of Set B:\n";

    for(int i = 0; i < m; i++)
    {
        cin >> B[i];
    }

    cout << "\nCartesian Product A x B:\n";

    cout << "{ ";

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            cout << "(" << A[i]
                 << "," << B[j] << ")";

            if(i != n - 1 || j != m - 1)
            {
                cout << ", ";
            }
        }
    }

    cout << " }\n";

    return 0;
}

---

Sample Output (C++)

Enter number of elements in Set A: 2

Enter elements of Set A:
1 2

Enter number of elements in Set B: 2

Enter elements of Set B:
3 4

Cartesian Product A x B:
{ (1,3), (1,4), (2,3), (2,4) }

---

C++ STL Approach

The Cartesian Product can also be displayed using C++ vectors and nested loops. The important idea remains the same: every element of the first set is combined with every element of the second set.

#include <iostream>
#include <set>

using namespace std;

int main()
{
    set<int> A = {1, 2};
    set<int> B = {3, 4};

    cout << "A x B = { ";

    for(int a : A)
    {
        for(int b : B)
        {
            cout << "(" << a << "," << b << ") ";
        }
    }

    cout << "}\n";

    return 0;
}

---

Java Program

The following Java program uses nested loops to generate every ordered pair of the Cartesian Product.

/* Java Program to Find Cartesian Product of Two Sets */

import java.util.Scanner;

public class CartesianProduct
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);

        System.out.print("Enter number of elements in Set A: ");
        int n = sc.nextInt();

        int[] A = new int[n];

        System.out.println("Enter elements of Set A:");

        for(int i = 0; i < n; i++)
        {
            A[i] = sc.nextInt();
        }

        System.out.print("Enter number of elements in Set B: ");
        int m = sc.nextInt();

        int[] B = new int[m];

        System.out.println("Enter elements of Set B:");

        for(int i = 0; i < m; i++)
        {
            B[i] = sc.nextInt();
        }

        System.out.println("\nCartesian Product A x B:");

        System.out.print("{ ");

        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                System.out.print("(" + A[i] + "," + B[j] + ")");

                if(i != n - 1 || j != m - 1)
                {
                    System.out.print(", ");
                }
            }
        }

        System.out.println(" }");

        sc.close();
    }
}

---

Sample Output (Java)

Enter number of elements in Set A: 2

Enter elements of Set A:
1 2

Enter number of elements in Set B: 2

Enter elements of Set B:
3 4

Cartesian Product A x B:
{ (1,3), (1,4), (2,3), (2,4) }

---

Python Program

The following Python program generates the Cartesian Product using nested loops.

# Python Program to Find Cartesian Product of Two Sets

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

result = set()

for a in A:

    for b in B:

        result.add((a, b))

print("Set A =", A)

print("Set B =", B)

print("Cartesian Product A x B =", result)

---

Sample Output (Python)

Set A = {1, 2}

Set B = {3, 4}

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

---

Python Using itertools.product()

Python provides the product() function in the itertools module for generating Cartesian Products.

# Python Program using itertools.product()

from itertools import product

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

result = product(A, B)

print("Set A =", A)

print("Set B =", B)

print("Cartesian Product A x B:")

for pair in result:

    print(pair)

---

Python Using List Comprehension

The Cartesian Product can also be generated using Python list comprehension.

# Cartesian Product using List Comprehension

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

result = [(a, b) for a in A for b in B]

print("A x B =", result)

---

Python Program for User Input

# Cartesian Product using User Input

A = set(map(int, input("Enter elements of Set A: ").split()))

B = set(map(int, input("Enter elements of Set B: ").split()))

result = [(a, b) for a in A for b in B]

print("\nSet A =", A)

print("Set B =", B)

print("Cartesian Product A x B =")

print(result)

---

Dry Run

Consider:

A = {1, 2}

B = {3, 4}

Set A contains 2 elements and Set B contains 2 elements. Therefore:

|A × B| = 2 × 2 = 4

Step	Element from A	Element from B	Ordered Pair
1	1	3	(1,3)
2	1	4	(1,4)
3	2	3	(2,3)
4	2	4	(2,4)

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

---

Step-by-Step Dry Run

Step 1

Select the first element from A: 1

Combine it with every element of B:

(1,3)

(1,4)

---

Step 2

Select the second element from A: 2

Combine it with every element of B:

(2,3)

(2,4)

---

Time Complexity

Suppose Set A contains n elements and Set B contains m elements. The outer loop executes n times and the inner loop executes m times for every element of A. Therefore, the time complexity is:

O(n × m)

---

Space Complexity

If all ordered pairs are stored, the Cartesian Product contains n × m pairs. Therefore, the space required to store the result is:

O(n × m)

If the pairs are only displayed and not stored, the additional auxiliary space can be considered O(1), apart from the input sets.

---

Properties of Cartesian Product

• A × B contains ordered pairs.
• The first element of each pair comes from A.
• The second element of each pair comes from B.
• |A × B| = |A| × |B|.
• Generally, A × B ? B × A.
• If A or B is empty, then A × B is empty.
• The Cartesian Product can be extended to more than two sets.

---

Difference Between A × B and B × A

Operation	Result
A × B	{(1,3),(1,4),(2,3),(2,4)}
B × A	{(3,1),(3,2),(4,1),(4,2)}

Therefore:

A × B ? B × A

---

Applications

• Database Operations
• Relational Algebra
• SQL CROSS JOIN
• Combinatorial Problems
• Probability
• Graph Theory
• Artificial Intelligence
• Machine Learning
• Data Analysis
• Generating Possible Combinations

---

Advantages

• Simple to understand and implement.
• Systematically generates all possible ordered pairs.
• Useful in relational database operations.
• Useful in combinatorial problems.
• Can be implemented easily using nested loops.

---

Disadvantages

• The number of pairs can become very large.
• Time complexity is O(n × m).
• Storing a large Cartesian Product requires considerable memory.
• The result may grow rapidly when both sets are large.

---

Viva Questions

1. What is a Cartesian Product?
2. How is Cartesian Product represented?
3. What is an ordered pair?
4. What is A × B?
5. What is the difference between A × B and B × A?
6. How many ordered pairs are present in A × B?
7. What is the formula for the cardinality of Cartesian Product?
8. What happens when one of the sets is empty?
9. What is the time complexity of Cartesian Product?
10. Where is Cartesian Product used?

---

Frequently Asked Interview Questions

1. What is Cartesian Product?
   The Cartesian Product of two sets is the set of all ordered pairs formed by taking every element of the first set with every element of the second set.


2. What is the formula for the Cartesian Product?
   A × B = {(a,b) | a ? A and b ? B}


3. If |A| = 3 and |B| = 4, how many elements are present in A × B?
   3 × 4 = 12


4. Is A × B equal to B × A?
   Generally, no. Cartesian Product depends on the order of the sets.


5. What is the time complexity of generating A × B?
   O(n × m), where n and m are the sizes of the two sets.


6. What happens if A is an empty set?
   The Cartesian Product is an empty set.
   
   Ø × B = Ø


7. Where is Cartesian Product used in databases?
   It forms the basis of the Cartesian product operation in relational algebra and is related to the SQL CROSS JOIN operation.

---

Practice Questions

1. Write a C program to find the Cartesian Product of two sets.
2. Write a C++ program to find the Cartesian Product.
3. Write a Java program to find the Cartesian Product.
4. Write a Python program to find the Cartesian Product.
5. Find A × B for A = {1,2} and B = {3,4}.
6. Find B × A for the above sets.
7. If |A| = 4 and |B| = 5, find |A × B|.
8. Explain why A × B is generally not equal to B × A.
9. Find the Cartesian Product when one set is empty.
10. Implement Cartesian Product without using built-in functions.

---

---

Summary

The Cartesian Product of two sets produces all possible ordered pairs by combining every element of the first set with every element of the second set. If Set A contains n elements and Set B contains m elements, then A × B contains n × m ordered pairs. In this experiment, the Cartesian Product has been implemented using C, C++, Java and Python. Nested loops are used to systematically combine every element of the first set with every element of the second set. The time complexity of the basic implementation is O(n × m).

---

---

---

❮ Previous    Next ❯

---

---