What is the process of calculating the cartesian product using TypeScript?

Question

What is the process of calculating the cartesian product using TypeScript?

My desired type signature is as follows:

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
}

For example, with the input:

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

The expected output would be:

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

Attempting to use this reference implementation results in a type problem:

https://i.sstatic.net/CRJGX.png

Here's a link to the TypeScript playground for reference.

javascript typescript functional-programming permutation ramda.js

Answer 1

Answer №1

If you're interested in leveraging Ramda, consider utilizing R.sequence specifically with arrays.

const combine = R.sequence(Array.of)

const data = [
  [ 'x', 'y' ],
  [ 3, 4 ]
];

combine(data)
//=> [["x", 3], ["x", 4], ["y", 3], ["y", 4]]

Answer 2

If you're interested in leveraging Ramda, consider utilizing R.sequence specifically with arrays.

const combine = R.sequence(Array.of)

const data = [
  [ 'x', 'y' ],
  [ 3, 4 ]
];

combine(data)
//=> [["x", 3], ["x", 4], ["y", 3], ["y", 4]]

Answer 3

Answer №2

When approaching problems like this, my go-to is always to begin by identifying the types involved.

Firstly, a type is defined to extract the element type of an array:

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

Although A[number] exists, using this will lead to type errors later on due to the nature of A being a result from infer.

Next, a type is created that takes a list of arrays and provides their respective element types:

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

This is akin to

Inputs.map((F) => ElementType(F))

in actual code.

Finally, utilizing the aforementioned types, a CartesianProduct type is established:

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

Now, having laid out the groundwork with types, it's time to translate this into executable code:

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

The impeccable implementation presented here was sourced from this fantastic answer, which also offers alternative solutions if your environment does not support flat or flatMap.

Once we have implemented the function, we then 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())));
}

However, an error arises because the return type does not align with the type expected by the reduce function. Unfortunately, I do not know an elegant solution to eliminate this 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

Answer 4

When approaching problems like this, my go-to is always to begin by identifying the types involved.

Firstly, a type is defined to extract the element type of an array:

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

Although A[number] exists, using this will lead to type errors later on due to the nature of A being a result from infer.

Next, a type is created that takes a list of arrays and provides their respective element types:

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

This is akin to

Inputs.map((F) => ElementType(F))

in actual code.

Finally, utilizing the aforementioned types, a CartesianProduct type is established:

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

Now, having laid out the groundwork with types, it's time to translate this into executable code:

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

The impeccable implementation presented here was sourced from this fantastic answer, which also offers alternative solutions if your environment does not support flat or flatMap.

Once we have implemented the function, we then 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())));
}

However, an error arises because the return type does not align with the type expected by the reduce function. Unfortunately, I do not know an elegant solution to eliminate this 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

What is the process of calculating the cartesian product using TypeScript?

Answer №1

Answer №2

Similar questions

Attempting to extract information from paginated asp pages using Scrapy Splash in the Python programming language

Tips for implementing a reusable instance of a class in (SSR) React (comparable to a @Bean in Spring)

Transitioning effects for Carousel in Bootstrap 4 Beta using Fade technique

Laravel is displaying an error message stating "undefined index:year" despite the fact that the field is

Showing the current HTML page using JavaScript when clicking?

Error encountered when making Ajax request to WCF service: receiving an Object object

What is the best way to showcase JSON data while incorporating HTML tags in a React application?

Making a surface-level copy of an array containing nested arrays

Postman's ability to capture elements that meet specific criteria set by another element

The json.stringify method is inserting additional backslashes into the response sent by res.send()

What are the steps for implementing Babel in a CLI program?

Organizing menu options into subcategories using jQuery UI for easy sorting

js.executeScript produces a Unexpected identifier error

Custom attribute in ReactJS component - I am not defined in my custom attribute in React component

The checkbox function is malfunctioning when integrated with JavaScript

What is the best way to develop interactive components using Google App Scripts for Google Sites?

struggling to set dropdown select value within an AngularJS controller

The act of transferring non-textual information into web-based applications

Having difficulty capturing an error related to an invalid form body in discord.js

transferring information back and forth between a javascript array and php