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);
};

typescript version of ref http://stackoverflow.com/a/43053803/176868

Super helpful code!
Quick correction; Line 10 should be return cartesianProduct(fab, b2, ...c2);

 Types of property 'slice' are incompatible.
   Type '(start?: number | undefined, end?: number | undefined) => never[][]' is not assignable to type '(start?: number | undefined, end?: number | undefined) => never[]'.
     Type 'never[][]' is not assignable to type 'never[]'.
       Type 'never[]' is not assignable to type 'never'.

36     [].concat(...a.map(a2 => b.map(b2 => [].concat(a2, b2))));

An improved version that removes the need for any types...

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

Test cases...

import { cartesianProduct } from "./lists";

describe('cartesianProduct tests', () => {    
    it('test one', () => {
        expect(cartesianProduct([1], [])).toEqual([1]);
        expect(cartesianProduct([1], [2])).toEqual([[1, 2]]);
        expect(cartesianProduct([1], [2], [3])).toEqual([[1, 2, 3]]);
        expect(cartesianProduct([1, 2], [2], [3])).toEqual([[1, 2, 3], [2, 2, 3]]);
        expect(cartesianProduct([1], [2, 4], [3])).toEqual([[1, 2, 3], [1, 4, 3]]);
        expect(cartesianProduct([1], [2], [3, 5])).toEqual([[1, 2, 3], [1, 2, 5]]);
        expect(cartesianProduct([1, 2], [10, 20], [100, 200, 300])).toEqual([ [ 1, 10, 100 ],
            [ 1, 10, 200 ],
            [ 1, 10, 300 ],
            [ 1, 20, 100 ],
            [ 1, 20, 200 ],
            [ 1, 20, 300 ],
            [ 2, 10, 100 ],
            [ 2, 10, 200 ],
            [ 2, 10, 300 ],
            [ 2, 20, 100 ],
            [ 2, 20, 200 ],
            [ 2, 20, 300 ] ]);
    });
});

@ssippe The version above errors in TypeScript 3.5.1: http://www.typescriptlang.org/play/#code/MYewdgzgLgBAZjAvDAPAFQHwAoCGAuGNAbQF0AaGAIwOJIEokMZSA6UMYHKLF3nFgLY4ADlgAmjKoJFYAppNbtO3MRVl0NdANwAoWQA9hIAE6x20GJ1OyIASxxgACsZBiArsFjJ02fIVIU1P7kMLxsNKSkDIhMAN46MIkwtghYAISUMAA+WVIANrJgAOZQABaIFQAMdAlJdcayUG7GYDA4unXmsHA4mchwuIHatYldzJQATBRhwBMkSJYdSQ1NLZY41nYOzq4e3D2UgVOWE8MAvlpAA.

Alternative, from https://stackoverflow.com/a/12628791/2743091, modified a little bit for a more concise syntax and compliant with Typescript:

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), []),
    [[]]
  )
}

Usage:

const result = cartesianProduct([1, 2, 3], [4, 5, 6], [7, 8])

expect(result).toEqual([
  [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]
])

Much better. 👍

Very nice functional style, bravo! It is also an option to use [...result, entry] instead of concat (arguably "nicer" ;-)

This is great, thanks!

In case anyone else is getting errors, in order to get it to work I had to add a comma at the end of line 6:

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), []), // <-------------
    [[]]
  )
}

Thanks everyone! Just thought I would include another version with spread operator instead of concat.

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

Using lodash:

import reduce from 'lodash/reduce';
import map from 'lodash/map';
import concat from 'lodash/concat';
import flatMap from 'lodash/flatMap';

/**
 * @see https://stackoverflow.com/a/44046650/592760
 */
const cartesianProductOf = <T>(...args: T[][]): T[][] =>
    reduce<T[], T[][]>(args, (results, array) => flatMap(map(results, (x) => map(array, (y) => concat(x, [y])))), [[]]);

export { cartesianProductOf };

Simplest solution I found using vanilla JS (which happens to be nearly identical to the previous comment)

const cartesianProduct = <T,>(...sets: T[][]) =>
    sets.reduce<T[][]>((accSets, set) => accSets.flatMap(accSet => set.map(value => [...accSet, value])), [[]]);

One of my teammates found this one and seems to get 50x+ better perf (owid/owid-grapher#783):

https://github.com/ehmicky/fast-cartesian/blob/main/src/main.js

It's a very unusual approach that I personally haven't dug into yet but curious why it would be so fast.

Reduce is slow, it could explain the difference.

If you need cartesian product on very large collections, yes, you should sacrifice the beauty of the functional solution by the "dirty" one :)

None of this solves the problem of the types, which is the only hard thing about cartesian products in TypeScript. For example, if my inputs has the type Array<number[], string[]>, I need the solution to have the type Array<[number,string]>.

None of the solutions here offer that, at which point I am better off using JavaScript.

Regarding the slowness of some solutions: it doesn't have to do with .reduce at all, which is only slightly slower than a for loop. Instead, the spread operator has linear complexity, and hence the solution with .reduce has quadratic complexity. I bet that the solution that @breck7 linked (which is no longer available) does not use the spread operator.

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())))