Typescript Cartesian Product

cartesianProduct.ts

const f = (a: any[], b: any[]): any[] =>
    [].concat(...a.map(a2 => b.map(b2 => [].concat(a2, b2))));

export const cartesianProduct = (a: any[], b: any[], ...c: any[]) => {    
    if (!b || b.length === 0) {
        return a;
    }
    const [b2, ...c2] = c;
    const fab = f(a, b);
    return cartesianProduct(fab, b2, c2);
};

Seems working:

Output:

[
  [ '1', '4', '7' ], [ '1', '4', 8 ],
  [ '1', 5, '7' ],   [ '1', 5, 8 ],
  [ '1', 6, '7' ],   [ '1', 6, 8 ],
  [ 2, '4', '7' ],   [ 2, '4', 8 ],
  [ 2, 5, '7' ],     [ 2, 5, 8 ],
  [ 2, 6, '7' ],     [ 2, 6, 8 ],
  [ 3, '4', '7' ],   [ 3, '4', 8 ],
  [ 3, 5, '7' ],     [ 3, 5, 8 ],
  [ 3, 6, '7' ],     [ 3, 6, 8 ]
]

I bet that the solution that @breck7 linked (which is no longer available) does not use the spread operator.

The code from https://github.com/ehmicky/fast-cartesian/blob/main/src/main.js was moved to https://github.com/ehmicky/fast-cartesian/blob/c0aa513aab291e16a380299ec0ce1dd121ec4315/src/main.ts and pasted below for posterity. The author's explanation of perf improvements is at owid/owid-grapher#783 (comment).

// [License = Apache-2.0](https://github.com/ehmicky/fast-cartesian/blob/c0aa513aab291e16a380299ec0ce1dd121ec4315/LICENSE), from https://github.com/ehmicky
import { validateInputs, type Inputs } from './validate.js'

/**
 * Returns a two-dimensional `Array` where each row is a combination of
 * `inputs`.
 *
 * @example
 * ```js
 * console.log(
 *   fastCartesian([
 *     ['red', 'blue'],
 *     ['circle', 'square'],
 *   ]),
 * )
 * // [
 * //   [ 'red', 'circle' ],
 * //   [ 'red', 'square' ],
 * //   [ 'blue', 'circle' ],
 * //   [ 'blue', 'square' ]
 * // ]
 *
 * // Return initial indexes
 * console.log(
 *   fastCartesian(
 *     [
 *       ['red', 'blue'],
 *       ['circle', 'square'],
 *     ].map(Object.entries),
 *   ),
 * )
 * // [
 * //   [ [ '0', 'red' ], [ '0', 'circle' ] ],
 * //   [ [ '0', 'red' ], [ '1', 'square' ] ],
 * //   [ [ '1', 'blue' ], [ '0', 'circle' ] ],
 * //   [ [ '1', 'blue' ], [ '1', 'square' ] ]
 * // ]
 * ```
 */
const fastCartesian = <InputArrays extends Inputs>(
  inputs: readonly [...InputArrays],
) => {
  validateInputs(inputs)
  const result = [] as CartesianProduct<InputArrays>

  if (inputs.length === 0) {
    return result
  }

  const loopFunc = getLoopFunc(inputs.length)
  loopFunc(inputs, result)
  return result
}

export default fastCartesian

type CartesianProduct<InputArrays extends Inputs> =
  InputArrays extends readonly []
    ? []
    : {
        [index in keyof InputArrays]: InputArrays[index] extends readonly (infer InputElement)[]
          ? InputElement
          : never
      }[]

const getLoopFunc = (length: number) => {
  const cachedLoopFunc = cache[length]

  if (cachedLoopFunc !== undefined) {
    return cachedLoopFunc
  }

  const loopFunc = mGetLoopFunc(length)
  // eslint-disable-next-line fp/no-mutation
  cache[length] = loopFunc
  return loopFunc
}

const cache: { [key: number]: LoopFunction } = {}

// Create a function with `new Function()` that does:
//   (arrays, results) => {
//     for (const value0 of arrays[0]) {
//       for (const value1 of arrays[1]) {
//         // and so on
//         results.push([value0, value1])
//       }
//     }
//   }
const mGetLoopFunc = (length: number) => {
  const indexes = Array.from({ length }, getIndex)
  const start = indexes
    .map((index) => `for (const value${index} of arrays[${index}]) {`)
    .join('\n')
  const middle = indexes.map((index) => `value${index}`).join(', ')
  const end = '}\n'.repeat(length)

  // eslint-disable-next-line no-new-func, @typescript-eslint/no-implied-eval
  return new Function(
    'arrays',
    'result',
    `${start}\nresult.push([${middle}])\n${end}`,
  ) as LoopFunction
}

const getIndex = (value: undefined, index: number) => String(index)

type LoopFunction = (arrays: Inputs, result: unknown[]) => void

@cr0cK it definitely does not work, as you can read in your screenshot. The output type is (number | string)[][], which is awful. The correct output type is [number,string][].

@SgtPooki Thanks for the link, that's also a nice read! The author is optimizing at a much lower level. The issue I was referring to (quadratic complexity due to the usage of the spread operator in loops) comes even before that. You don't need to understand much JavaScript to avoid quadratic complexity if possible :)

@albertodiazdorado It is not "awful", it is working as expected, as T can infer any type of value here.

Example with 3 different types:

If you want to enforce the type of each dimension of your array, you should consider functions overloading like this:

@cr0cK

export function cartesianProduct<T>(...allEntries: T[][]): T[][] {
    return allEntries.reduce<T[][]>(
      (results, entries) =>
        results
          .map(result => entries.map(entry => result.concat([entry])))
          .reduce((subResults, result) => subResults.concat(result), []),
      [[]]
    )
  }


const numbers = [1,2,3,4];
const strings = ["1", "2", "3", "4"];

// Argument of type 'string[]' is not assignable to parameter of type 'number[]'.
//  Type 'string' is not assignable to type 'number'.ts(2345)
const product = cartesianProduct(numbers, strings);

First of all, the inference is not working properly. But even if we aid the compiler, the types are still awful:

export function cartesianProduct<T>(...allEntries: T[][]): T[][] {
    return allEntries.reduce<T[][]>(
      (results, entries) =>
        results
          .map(result => entries.map(entry => result.concat([entry])))
          .reduce((subResults, result) => subResults.concat(result), []),
      [[]]
    )
  }


const numbers = [1,2,3,4];
const strings = ["1", "2", "3", "4"];

const product = cartesianProduct<number | string>(numbers, strings);

// Property 'length' does not exist on type 'string | number'.
//  Property 'length' does not exist on type 'number'.ts(2339)
console.log(product[0][1].length)

We know with certainty that the second element of the cartesian product is a string. However, your implementation loses that information. That's not what I expect from a type system. I want a type system to help me, not make my work harder.

That is how you "expect" it to work?

Indeed, the inference does not work with your example.

But my simple recommendation here:

Try to avoid mixing types when you can. Here for a cartesian product, I'm not sure it makes a lot of sense to mix strings and numbers.

I want a type system to help me, not make my work harder.

A type system is also here to help you to design things the right way. If the implementation becomes too complex, it generally means that something is wrong. You do not implement things the same way when using typings. If you're not happy with that, you should go back to JS.

Tell me that you cannot solve the problem of the cartesian product in TypeScript without telling me that you cannot solve the problem of the cartesian product in TypeScript.

Which is fine, by the way. I don't know the solution either. I came here looking for the solution and make the note that the proposed solution is wrong, in the sense explained in the comment above. Nothing else.

If you find the right solution, I'd be glad if you posted it here.

Mixed types are tricky.
Give this a try.

The key is [...T]

export const cartesianProduct = <T extends any[][]>(a: [...T]): Array<{[K in keyof T]: T[K][number]}> => a.reduce((a, b) => a.flatMap(d => b.map(e => [d, e].flat())))