Sets - Set Algebra

Have you ever seen "difference" or "union" available on data structures in your language of choice? Maybe they've been available on arrays, maybe on sets, but they all stem from Set Algebra. In this lesson we're going to look at four different operations of Set Algebra, and look at how to implement each one with more tests.

We're working on inlining examples! Until then, please find the examples here on GitHub.

Sets - Algebraic Operations

In our lesson about Sets, we took a quick review of basic operations for the set abstract data type, and then implemented it in JavaScript with a new class named MySet. We talked about tradeoffs of using a Map as the underlying data structure, speed expectations, and reasons why we'd want to use a set.

But that was just the tip of the iceberg. Depending on context you're using, sets can do so much more. In this lesson we're going to take a look at some of the most common pieces of Set Algebra, cover their usage, and then implement them with a new set of tests.

Many of these methods you've likely used before on arrays, but may not have known the definition, or where it came from.

So let's get started by checking out our test file. At the top I've added four algebraic operations on sets from the Wikipedia. Unfortunately, unless you know what these terms mean already, their definition is useless. So lets instead jump down to our new tests under the Set Algebra describe block and start learning. The first thing to point out is that our test subject will be an instance of MySet containing 1,2, and 3. And other will be a set containing 3, 4, and 5. These will be consistent for all tests in this section so I wanted to make it a point to make sure these were known before we jumped in. And now that that's out of the way, let's move on to the tests themselves.

// A ∪ B
// A1, A2,...,An + B1, B2,...Bn
// Set of all elements of A, B, or both.
it('can return the union of two sets', function() {
  expect(this.subject.union(this.other).equals(new MySet(1,2,3,4,5))).to.be.true;
});

The first test says that our set can return the union of two sets. That U looking symbol here is the mathematical representation for the union operation on sets. The union of two sets is effectively taking every element from A and B and placing them into a new set together. So we say that the union of set A and B is a set of all elements in A, B, or both. Even if the same element exists in both, by the definition of a set having unique elements, it'll only have one copy of each element.

If we run that test in isolation we can see that the method union does not exist, so in order to turn our test green and to get a better understanding of what a union is, we're going to implement that method now.

union(other) {
}

As we saw in the test, our union method takes another set as an argument, so we'll just call that other, as we did in our equals method above. And now we're going to define union in terms of JavaScript arrays for two reasons. One: I think it'll be easier to demonstrate the implementation using something you're already familiar with, and two: the virtual machine will be way better at optimizing this kind of operation than we would.

To do so we're going to return a new set created from a list. And to get a legitimate failure, we're going to create it from an empty array, and then run our tests.

union(other) {
  return MySet.createFrom([]);
}

Now we can see that the set we're returning is not equal to the set we should have - with equal defined as being the same length with the same elements.

So we're going to return the list form of our current set concatenated, or merged, with the array representation of our other set. Again, this is taking every element of the first set, every element from the other set, and putting them together into a new set.

union(other) {
  return MySet.createFrom(this.toList().concat(other.toList()));
}

If we run our tests again, we can now see our tests are green, because our test subject is a set containing 1,2, and 3, and the other set contains 3,4,5, and when unioned they return a set containing 1,2,3,4, and 5.

Okay so now that we've demonstrated unions, we can move on to the next operation - finding the intersection of two sets.

// A ∩ B
// Set of all elements that are in both A and B
it('can return the intersection of two sets', function() {
  expect(this.subject.intersection(this.other).equals(new MySet(3))).to.be.true;
});

The mathematical symbol for an intersection is the union symbol but upside down. And an intersection of two sets is a set containing all elements that are in both A and B. So, since as we just saw, our subject contains 1,2, and 3, and the other set contains 3, 4, and 5, we are asserting that our new set will only have 3, since that is the only element shared by both. As you'd expect our test is failing due to a missing method, so let's implement that now.

I'm going to copy the definition of union since it uses much of the same code, and also only accepts another set as an argument. Since we need to return another set from this operation based on a filtered list, we'll remove the method to concatenate two arrays, and instead filter our list to only elements that are present in the other using its has method and passing in the current element.

intersection(other) {
  return MySet.createFrom(this.toList().filter(e => other.has(e)));
}

Running our test shows that our returned set is now just a set returning the element 3, so we are free to move onto our third operation, finding the difference of two sets.

// A - B
// Set of all elements of A that are not in B
it('can return the difference of two sets', function() {
  expect(this.subject.difference(this.other).equals(new MySet(1,2))).to.be.true;
});

Finding the difference of set A and B is represented by the minus operator, which is very appropriate because the difference of A and B is a Set containing all elements of A that are not in B. So it's like A minus the elements of B.

We know the method doesn't exist, so let's do that now. I'm going to copy intersection, rename it to difference, and then run our tests just to prove that our set should not be the difference. And it's not. The reason I copied this one is because it is almost exactly the same. The only difference is that we want to filter on whether every element is not a member of the other.

difference(other) {
  return MySet.createFrom(this.toList().filter(e => !other.has(e)));
}

Running the tests again show that we are now passing, because we're returning a set containing only the elements of A that are not in B, 1 and 2.

And if we wanted to get all elements of B that are not in A, we'd just switch the sets around, so that b calls difference and passes in A.

There is another kind of difference we may want to get, we might want to find all elements in A and all elements in B, that are not present in both. You may know of this from standard logic as an exclusive or, or an XOR. Where if you're comparing two booleans, they evaluate to true if only one of the two booleans is true. For sets, this can also be represented as the difference of A and B unioned with the difference of B and A. We call this the symmetric difference.

// A ⊕ B => XOR operation
// A - B ∪ B - A
// Set of all elements of A and B that are not in both
it('can return the symmetric difference of two sets', function() {
  expect(this.subject.symmetricDifference(this.other).equals(new MySet(1,2,4,5))).to.be.true;
});

So when we are trying to find the symmetric difference of A, containing 1,2,3 and B, containing 3,4,5, our returned set should return 1,2,4, and 5, since 3 is a member of both A and B.

So let's implement the symmetricDifference function, which again will take the other set as its argument. And we are going to implement this operation in terms of existing operations, difference and union, like in our definition here.

A - B ∪ B - A

So we are going to return a set made of another, which will be the difference of this set and other unioned with the difference of other and this. Now when we run our tests...we're passing.

And that brings us to the end of this lesson. There are far more things we could cover on sets, but I think this is enough for you to go and experiment with for a while. Whether you decide to use these operations with arrays or sets in the future, I'm positive you'll find some good uses.