Cartesian product

CartesianProduct.ts

/**
  Cartesian product
  for example for input: [['x', 'y'], [1, 2 ]]
  we will have output: ['x1', 'x2', 'y1', 'y2']

  for example for input: [['x', 'y'], [1, 2, 3]]
  we will have output: ['x1', 'x2', 'x3', 'y1', 'y2', 'y3']

  1 1 -> 1
  1 2 -> 2
  2 2 -> 4
  2 3 -> 6
  3 3 -> 9
  n m -> n*m
  n m k -> n*m*k
  O(n^n)
**/

type Set = string[] | number[];

const getIndexes = (index: number, setsLength: number[]) => {
  const indexes = [index % setsLength[0]];
  let mathExpression = index;

  // O(n)
  for (let i = 1; i < setsLength.length; i++) {
    mathExpression = Math.floor(mathExpression / setsLength[i - 1]);
    indexes.push(mathExpression % setsLength[i]);
  }

  return indexes;
};

function cartesianProduct(sets: Set[]) {
  if (!sets.length) return [];
  if (sets.length === 1) return sets[0];

  const setsLength = sets.map((s) => s.length);
  const setsLenghtProduct = setsLength.reduce((a, b) => a * b, 1);

  const product = Array.from({ length: setsLenghtProduct });

  // O(n^n)
  for (let index = 0; index < setsLenghtProduct; index++) {
    // O(n)
    const setsIndexes = getIndexes(index, setsLength);

    let productPart = "";

    //
    for (let i = 0; i < setsIndexes.length; i++) {
      productPart += sets[i][setsIndexes[i]];
    }

    product[index] = productPart;
  }

  return product;
}

This works for any Cartesian size. However, if you know the size of your Cartesian, the simpler implementation will be faster. Here is an example of a simple n^4 implementation

    const product = [];
    for (let i = 0, globalItter = 0; i < sets[0].length; i++) {
      for (let j = 0; j < sets[1].length; j++) {
        for (let k = 0; k < sets[2].length; k++) {
          for (let l = 0; l < sets[3].length; l++, globalItter++) {
            product[globalItter] = `${sets[0][i]}${sets[1][j]}${sets[2][k]}${
              sets[3][l]
            }`;
          }
        }
      }
    }