Cartesian Product

Definition

Definition

The Cartesian Product Algorithm is a computational method used to find the Cartesian product of two or more sets. It generates all possible combinations of elements from these sets, creating a new set of tuples

Explanation

Guidance

• Iterate through each element of the first set
• For each element, iterate through each element of the second set
• Combine the elements into tuples
• If there are more sets, repeat steps 2-3 for each subsequent set
• Store the tuples in the Cartesian product set

Tips

• ensure efficient memory usage, especially for large sets, as the Cartesian product can grow exponentially
• optimize the algorithm by avoiding unnecessary iterations or redundant computations
• use appropriate data structures to store intermediate results and the final Cartesian product set efficiently

Practice

Practice

cartesianProduct(sets):
  // Initialize an empty list to store the Cartesian product
  cartesianSet = []

  // Initialize a list to keep track of the current index of each set
  currentIndex = [0] * length(sets)

  // Start with the first element of the first set
  generateCartesianProduct(sets, cartesianSet, currentIndex, 0)

  return cartesianSet

generateCartesianProduct(sets, cartesianSet, currentIndex, setIndex):
  // Base case: if all sets have been traversed, add the current combination to the Cartesian product
  if setIndex == length(sets):
    cartesianSet.append(getCurrentCombination(sets, currentIndex))
    return

  // Iterate over each element in the current set
  for i from 0 to length(sets[setIndex]) - 1:
    // Update the current index for the current set
    currentIndex[setIndex] = i

    // Recursively generate combinations for the next set
    generateCartesianProduct(sets, cartesianSet, currentIndex, setIndex + 1)

getCurrentCombination(sets, currentIndex):
  // Initialize an empty list to store the current combination
  combination = []

  // Iterate over each set and append the element at the current index to the combination
  for i from 0 to length(sets) - 1:
    combination.append(sets[i][currentIndex[i]])

  return combination

Solution

package main

func cartesianProduct(arrays [][]interface{}) [][]interface{} {
    if len(arrays) == 0 {
        return [][]interface{}{}
    }

    result := [][]interface{}{{}}

    for _, array := range arrays {
        var temp [][]interface{}
        for _, item := range array {
            for _, res := range result {
                t := append(res[:len(res):len(res)], item)
                temp = append(temp, t)
            }
        }
        result = temp
    }

    return result
}

import java.util.ArrayList;
import java.util.List;

public class Main {

  public static List<List<Object>> cartesianProduct(List<List<Object>> arrays) {
    List<List<Object>> result = new ArrayList<>();
    result.add(new ArrayList<>());

    for (List<Object> array : arrays) {
      List<List<Object>> temp = new ArrayList<>();
      for (Object item : array) {
        for (List<Object> res : result) {
          List<Object> t = new ArrayList<>(res);
          t.add(item);
          temp.add(t);
        }
      }
      result = temp;
    }

    return result;
  }
}

function cartesianProduct(arrays) {
  return arrays.reduce(
    (acc, array) => {
      return acc.flatMap((res) => {
        return array.map((item) => {
          return res.concat(item);
        });
      });
    },
    [[]],
  );
}

fun cartesianProduct(arrays: List<List<Any>>): List<List<Any>> {
    var result = listOf(emptyList<Any>())

    for (array in arrays) {
        val temp = mutableListOf<List<Any>>()
        for (item in array) {
            for (res in result) {
                val t = res.toMutableList()
                t.add(item)
                temp.add(t)
            }
        }
        result = temp
    }

    return result
}

def cartesian_product(arrays):
    result = [[]]
    for array in arrays:
        result = [x + [y] for x in result for y in array]
    return result

fn cartesian_product(arrays: &[Vec<&str>]) -> Vec<Vec<&str>> {
    let mut result = vec![vec![]];
    for array in arrays {
        let mut temp = vec![];
        for item in array {
            for res in &result {
                let mut t = res.clone();
                t.push(item);
                temp.push(t);
            }
        }
        result = temp;
    }
    result
}

function cartesianProduct<T>(arrays: T[][]): T[][] {
  return arrays.reduce(
    (acc, array) => {
      return acc.flatMap((res) => {
        return array.map((item) => {
          return [...res, item];
        });
      });
    },
    [[] as T[]],
  );
}