How to do cartesian product with TypeScript?-CodePudding

Here's the type signature that I'm after:

function cartesianProduct<T1, T2, T3, T4, T5, T6, T7, T8>([c1, c2, c3, c4, c5, c6, c7, c8]: [T1[], T2[], T3[], T4[], T5[], T6[], T7[], T8[]]): [T1, T2, T3, T4, T5, T6, T7, T8][];
function cartesianProduct<T1, T2, T3, T4, T5, T6, T7>([c1, c2, c3, c4, c5, c6, c7]: [T1[], T2[], T3[], T4[], T5[], T6[], T7[]]): [T1, T2, T3, T4, T5, T6, T7][];
function cartesianProduct<T1, T2, T3, T4, T5, T6>([c1, c2, c3, c4, c5, c6]: [T1[], T2[], T3[], T4[], T5[], T6[]]): [T1, T2, T3, T4, T5, T6][];
function cartesianProduct<T1, T2, T3, T4, T5>([c1, c2, c3, c4, c5]: [T1[], T2[], T3[], T4[], T5]): [T1, T2, T3, T4, T5][];
function cartesianProduct<T1, T2, T3, T4>([c1, c2, c3, c4]: [T1[], T2[], T3[], T4[]]): [T1, T2, T3, T4][];
function cartesianProduct<T1, T2, T3>([c1, c2, c3]: [T1[], T2[], T3[]]): [T1, T2, T3][];
function cartesianProduct<T1, T2>([c1, c2]: [T1[], T2[]]): [T1, T2][];
function cartesianProduct<T>(sets: T[][]): T[][] {
  // implementation
}

Here's an example of what I expect it to do. Given:

const input = [
  [ 'a', 'b' ],
  [ 1, 2 ],
];

It would spit out:

const output = [
  [ 'a', 1 ],
  [ 'a', 2 ],
  [ 'b', 1 ],
  [ 'b', 2 ],
];

Trying to utilize this

Here's a playground.

CodePudding user response：

If you'd like to use Ramda, you can use R.sequence with arrays.

const cartesianProduct = R.sequence(Array.of)

const input = [
  [ 'a', 'b' ],
  [ 1, 2 ],
];

cartesianProduct(input)
//=> [["a", 1], ["a", 2], ["b", 1], ["b", 2]]

CodePudding user response：

For problems like these I always like to start with the types first.

First a type to extract the element type of an array:

type ElementType<A> = A extends ReadonlyArray<infer T> ? T : never;

Yes, I know A[number] exists but this will result in type errors later on because A will be a result from infer.

Then a type that takes a list of arrays and gives us their element types.

type ElementsOfAll<Inputs, R extends ReadonlyArray<unknown> = []> = Inputs extends readonly [infer F, ...infer M] ? ElementsOfAll<M, [...R, ElementType<F>]> : R;

It's almost like Inputs.map((F) => ElementType(F)) in code.

Finally we use this type to define a CartesianProduct type:

type CartesianProduct<Inputs> = ElementsOfAll<Inputs>[];

Now that we did it in types it's time to do it in code:

function cartesianProduct(sets) {
  return sets.reduce((a, b) => a.flatMap(d => b.map(e => [d, e].flat())));
}

This amazing implementation was taken from this excellent answer where you can find other alternatives if your environment does not support flat or flatMap.

After we have this implementation we add the types:

function cartesianProduct<Sets extends ReadonlyArray<ReadonlyArray<unknown>>>(sets: Sets): CartesianProduct<Sets> {
  return sets.reduce((a, b) => a.flatMap(d => b.map(e => [d, e].flat())));
}

But there is an error because the return type does not match the type of the reduce call. Unfortunately I don't know a good way to rid the error but if a cast is acceptable:

function cartesianProduct<Sets extends ReadonlyArray<ReadonlyArray<unknown>>>(sets: Sets): CartesianProduct<Sets> {
  return sets.reduce((a, b) => a.flatMap(d => b.map(e => [d, e].flat()))) as CartesianProduct<Sets>;
}

Playground