Today’s DevAdvent 2022 issue is about set theory. Given two arrays of elements, how do I find their difference? There is a very easy way to do this. And also to do the intersection of two arrays and to calculate their geometric difference.

### The Problem: Array.diff()

link to the Kata

Your goal in this kata is to implement a difference function, which subtracts one list from another and returns the result.

It should remove all values from list `a`

, which are present in list `b`

keeping their order.

```
array_diff({1, 2}, 2, {1}, 1, *z) == {2} (z == 1)
```

If a value is present in b, all of its occurrences must be removed from the other:

```
array_diff({1, 2, 2, 2, 3}, 5, {2}, 1, *z) == {1, 3} (z == 2)
```

### Array.diff(): `A \ B`

(also written `A − B`

)

But let’s start with the basic problem. To solve it I start from the Wikipedia definition of difference between sets:

Given any two sets `A`

and `B`

, the set difference `A \ B (also written A − B)`

is the set of all things that belong to `A`

but not `B`

. Especially when `B`

is a subset of `A`

, it is also called the relative complement of `B`

in `A`

.

I can translate this definition into an algorithm:

- for each element of A
- check if it belongs to B
- if it doesn’t belong to B, go to the next element
- if it belongs to B, I delete it from A

I can also rewrite it in the form:

- filter every element of A that does not belong to B

At this point I have everything I need. I can use Array.filter() method to select values. And decide to filter all values based on the result of Array.includes() method:

```
export const arrayDiff = (a: number[], b: number[]): number[] =>
a.filter((x) => !b.includes(x));
```

### Array.intersect(): `A ∩ B`

After solving the basic problem, I can have fun and try adding more operations with arrays and sets. Pass at the intersection of the sets:

Given any two sets `A`

and `B`

, their intersection `A ∩ B`

is the set of all things that are members of both `A`

and `B`

. If `A ∩ B = ∅`

, then A and B are said to be disjoint.

I can translate this definition into an algorithm:

- for each element of A
- check if it belongs to B
- if it doesn’t belong to B, I delete it from A
- if it belongs to B, go to the next element

I can also rewrite it in the form:

- filter every element of A that does belong to B

```
export const arrayIntersect = (a: number[], b: number[]): number[] =>
a.filter((x) => b.includes(x));
```

### Array.union(): `A ∪ B`

Joining two sets is a simple problem in JavaScript. But before the solution, the definition:

Given any two sets `A`

and `B`

, their union `A ∪ B`

is the set of all things that are members of `A`

or `B`

or both.

In this case there is the Array.concat() method which allows you to join two arrays:

```
export const arrayUnion = (a: number[], b: number[]): number[] => a.concat(b);
```

### Array.symDiff(): `A Δ B`

The next operation is the symmetric difference. Wikipedia defines it like this:

Given any two sets `A`

and `B`

, their symmetric difference `A Δ B`

is the set of all things that belong to A or B but not both. One has to be a member of A and not a member of B, or a member of B and not a member of A: `A Δ B = (A \ B) ∪ (B \ A)`

.

In fact it is an operation composed of two different ones. I can write it like this:

```
export const arraySymDiff = (a: number[], b: number[]): number[] =>
arrayUnion(arrayDiff(a, b), arrayDiff(b, a));
```

Or if I prefer to use an extended notation:

```
export const arraySymDiff = (a: number[], b: number[]): number[] =>
a.filter((x) => !b.includes(x)).concat(b.filter((x) => !a.includes(x)));
```

### Array.cartesian(): `A × B`

The last operation to deal with is the Cartesian product of two arrays. Wikipedia defines it like this:

Given any two sets `A`

and `B`

, their cartesian product `A × B`

is the set of all ordered pairs `(a,b)`

such that `a`

is an element of `A`

and `b`

is an element of `B`

.

In other words, it is an operation that allows you to generate all possible pairs of the elements of two arrays.

I can solve the problem with a function like this:

```
export const arrayCartesian = (a: number[], b: number[]): number[][] =>
a.map((x) => b.map((y) => [x, y])).flat();
```

Or with this:

```
const arrayCartesian = (a: number[], b: number[]): number[][] =>
a.reduce((p, x) => [...p, ...b.map((y) => [x, y])], []);
```

### Conclusion

Finally I can add these functions to the prop. This way I can use them directly with each array:

```
Array.prototype.diff = function (arr2) {
return this.filter((x) => !arr2.includes(x));
};
Array.prototype.intersect = function (arr2) {
return this.filter((x) => arr2.includes(x));
};
Array.prototype.union = function (arr2) {
return this.concat(arr2);
};
Array.prototype.symDiff = function (arr2) {
return this.diff(arr2).concat(arr2.diff(this));
};
Array.prototype.cartesian = function (arr2) {
return this.reduce((p, x) => [...p, ...arr2.map((y) => [x, y])], []);
};
[1, 2, 3].diff([2, 3]);
[1, 2, 3].intersect([2, 3]);
[1, 2, 3].union([2, 3]);
[1, 2, 3].symDiff([2, 3]);
[1, 2, 3].cartesian([2, 3]);
```