DEV Community

loading...

Math Concepts for Programming - Sets

rafaelcalpena profile image Rafael Calpena ・5 min read

Today, I'm starting a series of posts about object relationships. In this post, we are going to see a foundational concept in Mathematics called Set. Let's check some use case examples and operations that can be applied to them.

Sets are "The Building Blocks"

A set is a well-defined collection of distinct objects.

The objects that belong to a set are called its elements (or points or members)

Source: Functional Analysis by P. K. Jain, Khalil Ahmad, and Om P. Ahuja

An informal way of defining a Set is a container (box/circle) that has distinct objects inside. We can represent it with the following notation:

S = {1, 2, 'some string'}
  • The elements of the Set are written inside the curly braces. S is an identifier to the Set.

The order of the objects does not matter.

S = {1, 2, 3} = {2, 3, 1} = {3, 2, 1}
  • The definition of Set does not allow for repetition of the same element, so each element should be represented at most once.
S = {1, 1, 2, 3, 2, 3} = {1, 2, 3}

Uses

We can use Sets to define the world around us.

  • The set of states in a country.
States = {'New York', 'California', 'Florida', 'Washington DC', ...} // size = 50
  • The set of username ids who have used your website this week.
usersFromLastWeek = {12938, 89032, 55866}
  • The empty set.
S = {}

Sets can also represent more complex cases.

  • The set of natural numbers (infinite).
S = {1, 2, 3, 4, ...} // Size = Infinity
  • The set of sets mentioned above.
S = { 
    {'New York', 'California', 'Florida', 'Washington DC', ...},
    {12938, 89032, 55866},
    {}
} // Size = 3
  • Self-containing sets.
S = {1, 2, S} =
{
    1, 2,
    { // S
        1, 2, { // S
            1, 2, {...}
        }
    }
} // Size = 3

💡 Elements contained in nested Sets are not considered direct elements from the Root Set (S).

Properties

  • Size = Number of elements present in the Set.

Operations

Operations are ways to read and/or transform the Set into another Set (or another object):

💡 The notation below is pseudo-code

  • Is Empty to check if Set size equals zero.
S1 = {}
isEmpty(S1) // = true
S2 = {1, 2, 3}
isEmpty(S2) // = false
  • Add one or more elements to the Set.
S1 = {1, 2}; 
S2 = add(S1, 3, 10); // = {1, 2, 3, 10};
  • Remove one or more elements from the Set.
S1 = {'a', 'b', 'c', 'd'}; 
S2 = remove(S1, 'c') // = {'a', 'b', 'd'}
  • Has to check if an element is contained in the Set.
S1 = {'a', 'b', 'c', 'd'}; 
has(S1, 'e') // False
has(S1, 'a') // True
  • Iterate to loop over elements in the Set.
S1 = {'Sandra', 'Mary', 'Louis'};
for (let person of S1) {
    // person = Sandra, Mary and Louis, respectively
    // Order may vary
}
  • Equals for comparing if one Set contains the exact same elements as another Set.
S1 = {'first', 'second', 'third'}
S2 = {'second', 'third', 'first'} // Order does not matter
equals(S1, S2) // True
S3 = {'fourth'}
equals(S1, S3) // False
  • Union: Creates a resulting Set that contains all elements from both Sets.
S1 = {'first', 'second', 'third'}
S2 = {'fourth'}
union(S1, S2) // = {'first', 'second', 'third', 'fourth'}
  • Difference: Creates a resulting Set with elements in Set1 that are not contained in Set2.
S1 = {'first', 'second', 'third'}
S2 = {'second'}
difference(S1, S2) // = {'first', 'third'}
  • Intersection: Creates a resulting set that contains only elements both present in Set1 and Set2
S1 = {'first', 'second', 'third'}
S2 = {'second', 'fourth'}
intersection(S1, S2) // = {'second'}
  • Disjoint: 2 sets are disjoint if their intersection is equal to the empty set.
S1 = {1, 2, 3}
S2 = {4, 5, 6}
areDisjoint(S1, S2) // = True

S3 = {3, 9, 10}
areDisjoint(S1, S3) // = False, because of "3"
areDisjoint(S2, S3) // = True
  • Filter for getting a set of only the elements that satisfy a given condition. The elements that do not satisfy the condition are not part of the result.
S1 = {1, 2, 3, 4, 5, 6}
numberIsEven = (number) => number % 2 === 0;
S2 = filter(S1, numberIsEven) // = {2, 4, 6}
  • Map for mapping Set elements into other elements
S1 = {1, 2, 3, 4, 5}
S2 = map(S1, (number) => number * 9)) // = {9, 18, 27, 36, 45}
  • Reduce for iterating on the Set and creating a new result. It takes an accumulator and item and returns a new value for the accumulator.
S1 = {1, 2, 3, 4, 5}
reduce (S1, (count, element) => count + element, 0) // Sum all elements, = 15
  • Symmetric Difference for obtaining the elements that are in either of the Sets, but not in both of them.
S1 = {1, 2, 3, 4}
S2 = {2, 4, 5, 6}
S3 = symmetricDifference(S1, S2) // = {1, 3, 5, 6}
  • Is Superset For checking whether one Set contains all elements of the other Set.
S1 = {1, 2, 3, 4}
S2 = {1}
isSuperset(S1, S2) // = true
S3 = {3, 4}
isSuperset(S1, S3) // = true
S4 = {3, 4, 5}
isSuperset(S1, S4) // = false
  • is Subset For checking whether all elements of one Set are contained in another Set.
S1 = {1, 2, 3, 4}
S2 = {1}
isSubset(S2, S1) // = true
S3 = {3, 4}
isSubset(S3, S1) // = true
S4 = {3, 4, 5}
isSubset(S4, S1) // = false
  • Find: Used to find one element in the Set that satisfies some constraint.
S1 = {1, 2, 3, 4, 5}
element = find(S1, n => n > 3) // = 4 or 5 (order may vary)
  • Every: Check if all elements of the Set satisfy some constraint.
S1 = {1, 2, 3, 4, 5}
element = every(S1, n => n < 10) // = True

S1 = {1, 2, 3, 4, 5}
element = every(S1, n => n < 3) // = False, because of 4 and 5
  • Order two or more Sets by their sizes. Returns a tuple with size as the number of Sets provided.
S1 = {1, 2}
S2 = {0}
S3 = {4, 1, 2}

order(S1, S2) // (S2, S1, S3)
  • Changes: A way to compare 2 Sets and find which elements must be removed or added from the first set to become equal to the second set.
S1 = {1, 2, 3, 4, 5, 6}
S2 = {4, 5, 6, 7}
Changes(S1, S2) = ({1, 2, 3}, {7}) // Starting from S1, remove 1, 2 and 3, and add 7 to transform it to S2
  • Cartesian Product: Multiply two sets in order to create a set of ordered pairs
S1 = {'a', 'b', 'c'}
S2 = {0, 1}
S3 = cartesianProduct(S1, S2) // = { ('a', 0), ('a', 1), ('b', 0), ('b', 1), ('c', 0), ('c', 1) }

In the next post, we are going to take a deeper look at ordered pairs and its uses.

Bonus

Russell's Paradox - a.k.a. The Barber Paradox

Discussion (0)

pic
Editor guide