Skip to content

Set

Learning Objectives

At the end of this sub-unit, students should

  • understand set.
  • know the basic set operations.

Unordered Collection

So far, all our collections are ordered. Is there any collection that is unordered? The most basic one is a set. Like mathematical set, we do not care about where the element is in the set as long as we know that the element is in the set. In fact, like mathematical set, Python set do no contain duplicate values. The notation for Python set is also similar to mathematical set. Both uses curly brackets.

Syntax

The syntax for set is as follows.

1
{❬ expression ❭, ❬ expression ❭, ❬ expression ❭, ..., ❬ expression ❭}
  • Empty Set: set()      ({} is already used by dictionary)
  • Singleton: { expr }      (the comma at the end is not required, but possible)
  • General: { expr1, expr2, expr3 }      (can have as many expressions as needed)

Set

1
2
3
4
>>> {1, 2, 3}           # a set
{1, 2, 3}
>>> {1, 2, 3, 1, 2, 3}  # deduplication: i.e., keep only one
{1, 2, 3}

We may think that an empty set is denoted by {}. Unfortunately, that is not the case. This is because there is another data type that was implemented before set that uses curly bracket too. That data type is dictionary. So unfortunately, {} creates an empty dictionary. To construct an empty set, we need to use set().

Set

1
2
3
4
5
6
7
8
>>> {}
{}
>>> type({})
<class 'dict'>
>>> set()
set()
>>> type(set())
<class 'set'>

Set Operation

The standard set operations are available in Python except for the complement operation. It is impossible to have a complement of a set of {1} because there are an infinite number of integers possible in Python. Remember, integer have an arbitrary precision in Python.

If we have two sets \(S_1\) and \(S_2\), the visualization of the operations are shown below. In all cases, Python ensures all the values in the resulting sets are distinct. The deduplication is performed automatically by Python.

Set Operation

SetOp01

This is on top of a typical collection operations like in and not in.

Set Operation

1
2
3
4
5
6
>>> {1, 2, 3} | {2, 3, 4}
{1, 2, 3, 4}
>>> {1, 2, 3} & {2, 3, 4}
{2, 3}
>>> {1, 2, 3} - {2, 3, 4}
{1}

There is an implicit convention in Python that the operator + is intended to be an ordered combination operation like concatenation. When we concatenate 'abc' with 'def', the order matters. 'abc' + 'def' produces 'abcdef' while 'def' + 'abc' produces 'defabc'. On the other hand, the operator | is an unordered combination. So {1, 2, 3} + {4, 5, 6} does not work on set because by convention it should be ordered while set is unordered.

Unfortunately, given that a set is unordered, it does not make sense to ask what is the first element in the set. So indexing does not work on set. Similarly, slicing depends on indexing, so it does not work on set too.

Set Operations

1
2
3
4
5
6
>>> {1, 2, 3}[0]
TypeError: 'set' object is not subscriptable
>>> {1, 2, 3}[1:]
TypeError: 'set' object is not subscriptable
>>> {1, 2, 3} + {4, 5, 6}
TypeError: unsupported operand type(s) for +: 'set' and 'set'

Comparison

So here is the first difference from ordered collection: the notion of equality. The philosophy of Python is that two objects are equal if they carry the same meaning. Of course this is not always followed due to the limitation of the representation. For instance, 0.1 + 0.2 == 0.3 is False and 1 == '1' is also False.

In the case of set, two sets are equal if they have exactly the same elements in any order. So we expect {1, 2, 3} == {3, 2, 1} to return True. Similarly, since Python is performing deduplication, we expect {1, 2, 3} == {3, 2, 1, 2, 3} to also return True.

Set Equality

1
2
3
4
5
6
7
8
>>> {1, 2, 3} == {3, 2, 1}
True
>>> {1, 2, 3} == {3, 2, 1, 2, 3}
True
>>> {1, 2, 3} == {3, 2, 1, 4}
False
>>> {1, 2, 3} == {3, 2, 1, 0, 1, 2, 3}
False

To make things more concrete, we can explain the definition of equality on set by mimicking the behavior with list. We say that two list lst1 and lst2 that mimic the behavior of a set is equal if for every element in lst1 exist in lst2 and every element in lst2 exist in lst1. Put it another way, we can say that lst1 is not equal to lst2 if one (or both) of the following is satisfied.

  • There is an element in lst1 that does not exist in lst2.
  • There is an element in lst2 that does not exist in lst1.

Set Equality

1
2
3
4
5
6
7
8
def set_equality(lst1, lst2):
  for elem in lst1:       # Check if there is elem in lst1
    if elem not in lst2:  #   that does not exist in lst2
      return False
  for elem in lst2:       # Check if there is elem in lst1
    if elem not in lst1:  #   that does not exist in lst2
      return False
  return True

What about other relational operator? We can also map these to mathematical operations as follows. Consider two sets s1 and s2 that corresponds to \(S_1\) and \(S_2\).

Python Mathematics
s1 < s2 \(S_1 \subset S_2\)
s1 <= s2 \(S_1 \subseteq S_2\)
s1 > s2 \(S_1 \supset S_2\)
s1 >= s2 \(S_1 \supseteq S_2\) 
1
2
3
4
>>> {2, 3} < {2, 3}
False
>>> {2, 3} < {1, 2, 3, 4}
True

1
2
3
4
>>> {2, 3} <= {2, 3}
True
>>> {1, 2, 3, 4} <= {2, 3}
False

1
2
3
4
>>> {2, 3} > {2, 3}
False
>>> {1, 2, 3, 4} > {2, 3}
True

1
2
3
4
>>> {2, 3} >= {2, 3}
True
>>> {2, 3} >= {1, 2, 3, 4}
False

This connection to subset operation should be used with care. A common mistake is shown below.

Incomparable

When dealing with number, string, or tuple, we can replace not (x < y) with x >= y. However, this property is not true for set.

1
2
3
4
5
6
7
8
9
>>> x, y = {1, 2}, {2, 3}
>>> x
{1, 2}
>>> y
{2, 3}
>>> not (x < y)
True
>>> x >= y
False

Note that given two sets x and y, we cannot simply say that one of the following will always be true.

  • x < y
  • x == y
  • x > y

It is possible that all of them produce False. This means that x and y are incomparable.

Using Set

Set is useful when we need our data to be distinct. We had an example of this when we want to find the average intake. We needed the number of distinct years. Our solution was to check if the year is already recorded in the list. If not, we record the year.

1
2
3
4
5
6
# other code omitted
for row in data:
  if row[0] not in year:  # check if not already recorded
    year.append(row[0])   # record
# other code omitted
years = len(year)

Using set, the solution is easier to read.

1
2
3
only_years = map(lambda row: row[0], data)
distincts  = set(only_years)
years      = len(distincts)

In fact, it can be shorter at the cost of some readability.

1
years = len(set(map(lambda row: row[0], data)))

Pangram

Pangram

A pangram or holoalphabetic sentence is a sentence using every letter of a given alphabet at least once. Pangrams have been used to display typefaces, test equipment, and develop skills in handwriting, calligraphy, and typing.

The most famous pangram is probably the following short story about a fox and a dog.

The quick brown fox jumps over the lazy dog.

It has all characters in the alphabets from A to Z. The kind of pangram we are interested is slightly different. We want a more restricted set of alphabets. For example, if the set of alphabets is 'agimnopr', then 'programming' forms a pangram over the alphabet.

So now, to check if a word is a pangram, we need to check that each character in the set of alphabets appears in the word. But this is incomplete. We also need to check if each character in the word appears in the set of alphabets. Otherwise, we have an invalid word. For instance, using only the characters in the set of alphabet 'agimnopr', the word 'programmer' cannot be formed.

We can quickly see that a pangram occurs when the set of characters in the set of alphabets is equal to the set of characters in the word. As a side note, we can quickly convert any sequence into a set of element using the set(seq) constructor. So set('agimnopr') gives us {'a', 'g', 'i', 'm', 'n', 'o', 'p', 'r'}. The solution can then be written simply as follows.

Pangram

1
2
def pangram(alphabet, word):
  return set(alphabet) == set(word)