Learn
B4.1.5 | SETS AS AN ADT (HL ONLY)
01 | WHEN MEMBERSHIP MATTERS MORE THAN POSITION
A school wants to invite every student who attends Robotics or Coding, without sending duplicate invitations. A list of registration events can contain the same student several times. For the invitation membership, we need a collection in which each student ID occurs only once.
A set ADT represents a collection of distinct elements. Its core questions are whether an element belongs, how to add or remove it, and how its membership relates to another set. The abstract contract does not assign numbered positions to its elements.
Throughout this lesson, A is the Robotics membership {S01, S02, S03}, and B is Coding {S03, S04}. S03 belongs to both, but is still one student ID.
02 | TWO ESSENTIAL PROPERTIES
| Property | Meaning | Consequence |
|---|---|---|
| Uniqueness | An element is either present or absent; repeated additions do not create extra occurrences | Adding S02 twice leaves one S02 membership |
| Unordered nature | The ADT does not promise a sequence or an index position | {S01, S02} and {S02, S01} describe the same membership |
Unordered does not mean the computer must shuffle elements on every display. It means a caller should not rely on a particular iteration order unless a more specific implementation contract promises one.
A list can record order and repetition; a set deliberately represents membership without those features. Converting an event list to a set loses repeated occurrences and sequence information.
03 | DEFINE THE OPERATIONS AND POLICIES
| Operation | High-level meaning |
|---|---|
| contains(x) | Test whether x is a member |
| add(x) | Ensure x is present without duplicating it |
| remove(x) | Ensure x is absent; specify the missing-member policy |
| size | Count distinct members |
| union | Members in either input, including those in both |
| intersection | Members common to both inputs |
| difference A minus B | Members in A that are not in B |
| subset / superset | Test whether all members of one set occur in another |
The ADT describes the meaning; the language API chooses names, return values and error behaviour. Python add returns None, whereas Java Set.add returns whether membership changed. They can both implement the same uniqueness rule.
A missing-member removal can raise an exception, return False or do nothing, depending on the chosen operation. State which one your program uses.
04 | CONSTRUCT A PYTHON SET
robotics = {"S01", "S02", "S03"}
registrations = ["S01", "S02", "S01", "S03"]
unique_ids = set(registrations)
empty_ids = set()
print(sorted(unique_ids))
print(len(unique_ids))
# ['S01', 'S02', 'S03']
# 3
Braces containing elements create a set literal. set(iterable) constructs membership from an existing collection, collapsing repeats. An empty set is set(); empty braces {} create a dictionary instead.
sorted returns a separate list for predictable presentation. That does not give the set an index order or change its ADT contract. The examples use same-type string IDs so they can be sorted consistently.
05 | CONSTRUCT A JAVA SET
Set<String> robotics = new HashSet<>(
Arrays.asList("S01", "S02", "S03"));
Set<String> emptyIds = new HashSet<>();
System.out.println(robotics.size());
// 3
These statements belong inside a method such as main with java.util.Set, HashSet and Arrays imported. Set is the interface used by the variable; HashSet is the selected concrete implementation.
Use the complete program later if you want a file that runs immediately. HashSet does not promise iteration order. A TreeSet copy can provide sorted presentation for these comparable string IDs, but that is a separate ordered implementation choice.
06 | TEST MEMBERSHIP, NOT AN INDEX
robotics = {"S01", "S02", "S03"}
print("S02" in robotics)
print("S99" not in robotics)
# True
# True
Python in asks whether the element is a member. Java uses robotics.contains("S02"). Neither requires knowing where the implementation stores the member.
A Python set does not support robotics[0]. If a user needs a numbered display, create an appropriate sequence for presentation. Do not mistake the display’s first row for an intrinsic first member of the set.
07 | ADD A NEW OR EXISTING ELEMENT
robotics = {"S01", "S02", "S03"}
result = robotics.add("S02")
print(result, len(robotics))
robotics.add("S05")
print(sorted(robotics))
# None 3
# ['S01', 'S02', 'S03', 'S05']
Adding existing S02 leaves membership unchanged. Adding new S05 increases the distinct-member count. Python’s returned None does not tell you whether the element was already present; inspect membership or size if that matters.
In Java, add("S02") returns false when S02 is already present, while adding a new S05 returns true. Keep the distinction between an operation’s membership effect and its language-specific return value.
08 | REMOVE CAREFULLY WHEN MEMBERSHIP IS UNCERTAIN
robotics = {"S01", "S02", "S03"}
robotics.remove("S02")
robotics.discard("S99")
print(sorted(robotics))
try:
robotics.remove("S99")
except KeyError:
print("S99 was not registered")
# ['S01', 'S03']
# S99 was not registered
Python remove raises KeyError for an absent element. discard leaves membership unchanged without that missing-member error. Both mutate the original set and return None on normal completion.
Java Set.remove returns true when membership changed and false when the requested member was absent. A missing-ID policy is part of the application design: silently tolerating an absent member can be suitable for cleanup, while a registration screen might need to report it.
09 | UNION: IN A OR B, INCLUDING BOTH
a = {"S01", "S02", "S03"}
b = {"S03", "S04"}
either = a | b
print(sorted(either))
# ['S01', 'S02', 'S03', 'S04']
Union gathers every element present in at least one input. The overlapping member S03 appears once, so the union has four members rather than five.
Python a.union(b) is an equivalent method form. These expressions produce a new set and leave a and b unchanged. In Boolean terms, union membership is inclusive OR, not “exactly one”.
10 | INTERSECTION: IN A AND B
a = {"S01", "S02", "S03"}
b = {"S03", "S04"}
both = a & b
print(sorted(both))
# ['S03']
Intersection contains only the common members. It answers “Which students attend both clubs?” Python also offers a.intersection(b). The result can be empty when there is no overlap.
Union and intersection are commutative: swapping the two inputs does not change membership of the result. This is not true of ordinary difference.
11 | DIFFERENCE: THE DIRECTION MATTERS
a = {"S01", "S02", "S03"}
b = {"S03", "S04"}
print(sorted(a - b))
print(sorted(b - a))
# ['S01', 'S02']
# ['S04']
A minus B contains Robotics members who are not in Coding. B minus A answers the reverse question. These are different sets here, so do not swap the operands when translating a scenario.
Python also provides a.difference(b). Difference does not remove members from a unless you use a mutating form such as difference_update or -=.
12 | MAKE JAVA SET ALGEBRA NON-DESTRUCTIVE
Set<String> either = new HashSet<>(robotics);
either.addAll(coding);
Set<String> both = new HashSet<>(robotics);
both.retainAll(coding);
Set<String> roboticsOnly = new HashSet<>(robotics);
roboticsOnly.removeAll(coding);
These statements use the sets and imports from the complete Java program. addAll, retainAll and removeAll change the receiving set. Creating a copy first preserves the original club membership.
retainAll keeps only members also in the supplied collection; removeAll removes the supplied collection’s members. Assigning another variable to robotics would create an alias, not an independent set copy.
13 | SUBSETS: ALL OF THESE MEMBERS ARE INCLUDED
team = {"S01", "S03"}
robotics = {"S01", "S02", "S03"}
print(team.issubset(robotics))
print(team <= robotics)
print(robotics <= robotics)
# True
# True
# True
Team is a subset of Robotics because every Team member occurs in Robotics. Equality is allowed for an ordinary subset relation: every set is a subset of itself.
One shared member is insufficient to prove subset. {S01, S99} is not a subset of Robotics even though S01 is shared. Check every required membership.
14 | SUPERSETS AND PROPER RELATIONS
team = {"S01", "S03"}
robotics = {"S01", "S02", "S03"}
print(robotics.issuperset(team))
print(robotics >= team)
print(team < robotics)
print(robotics < robotics)
# True
# True
# True
# False
A superset relation reverses the subset view: Robotics is a superset of Team. A proper subset requires inclusion and inequality, so Team is a proper subset of Robotics but Robotics is not a proper subset of itself.
Java robotics.containsAll(team) tests whether Robotics is a superset of Team, equivalently whether Team is a subset of Robotics. For finite sets, adding a smaller-size check distinguishes a proper subset. The argument direction matters.
15 | EMPTY SETS, EQUALITY AND DISJOINTNESS
| Statement | Result | Reason |
|---|---|---|
| ∅ is a subset of A | True | There is no empty-set member missing from A |
| A is a superset of ∅ | True | The same inclusion rule viewed in reverse |
| A ∩ ∅ | ∅ | No members are shared |
| A ∪ ∅ | A | Empty membership adds nothing |
| A − A | ∅ | Every member is excluded by the second A |
Set equality compares membership, not order or variable names. Python uses ==; Java Set uses equals for set membership equality. Java == instead compares whether two references reach the same object.
Two sets are disjoint when their intersection is empty. Python a.isdisjoint(b) expresses this directly. A set can be empty without being an error: “no students attend both clubs” is a meaningful result.
16 | EXPLORE THE OPERATIONS VISUALLY
Enter IDs such as S01, S02 and S03, separated by commas. Whitespace around each ID is ignored, but IDs must match uppercase S followed by two digits. Blank input means an empty set; repeated IDs collapse to one membership. Results are displayed sorted for checking, not because the ADT promises that order.
Try identical sets, disjoint sets, an empty input and reversed difference. The table separates A-only, shared and B-only members so you can justify each answer from membership rather than memorising the picture.
17 | DO NOT CONFUSE A SET WITH AN ELEMENT
ids = {"S01", "S02"}
print("S01" in ids)
print({"S01"} <= ids)
print(set("S01"))
# True
# True
# The final set contains the characters S, 0 and 1.
"S01" is one string element. {"S01"} is a set containing that element. set("S01") iterates through the string, so it constructs a character set rather than a one-ID set.
For a one-element set, use {"S01"} or set(["S01"]). Membership and subset are different questions even when the examples seem to refer to one ID.
18 | UPDATES, ALIASES AND COPIES
a = {"S01", "S02"}
alias = a
copy = a.copy()
alias.add("S03")
print(sorted(a))
print(sorted(copy))
result = a | {"S04"}
print(sorted(a))
print(sorted(result))
# ['S01', 'S02', 'S03']
# ['S01', 'S02']
# ['S01', 'S02', 'S03']
# ['S01', 'S02', 'S03', 'S04']
alias and a refer to one mutable set. copy has a separate membership container. The union expression also creates a separate set. By contrast, a.update(other), intersection_update and difference_update mutate a.
This is a shallow copy: objects referenced as members are not recursively duplicated. The element restrictions still matter, and the immutable string IDs used here keep the example simple.
19 | CHOOSE VALID ELEMENTS AND CONSISTENT IDENTIFIERS
Python set requires hashable members, such as strings, integers and suitable immutable tuples. A mutable list or another mutable set cannot normally be a member of a Python set. A frozenset can provide an immutable set value when needed, though it is not required for the core examples.
The logical set ADT is not intrinsically restricted to one hashing mechanism; that restriction belongs to this implementation. Java HashSet similarly relies on consistent equals and hashCode behaviour. Changing a stored object in a way that changes its equality or hash behaviour can undermine lookup.
Define what counts as the same identifier. "S01" and "s01" are different Python strings. If the application requires case-insensitive IDs, normalise deliberately before storage rather than expect the set to guess that rule.
20 | COMPLETE PYTHON MEMBERSHIP APPLICATION
Save this as sets_demo.py and click Run. Both club inputs remain unchanged by the algebra operations. sorted is used only to make the displayed results reproducible.
robotics = {"S01", "S02", "S03"}
coding = {"S03", "S04"}
print("S02" in robotics)
robotics.add("S02")
print(len(robotics))
robotics.add("S05")
robotics.discard("S99")
robotics.remove("S05")
both = robotics & coding
either = robotics | coding
robotics_only = robotics - coding
coding_only = coding - robotics
print(sorted(both))
print(sorted(either))
print(sorted(robotics_only))
print(sorted(coding_only))
print({"S01", "S03"}.issubset(robotics))
print(robotics.issuperset({"S01", "S03"}))
print(robotics == {"S03", "S02", "S01"})
The output is True, 3, then [S03], [S01, S02, S03, S04], [S01, S02], [S04], followed by True, True, True. The actual Python list displays include quotes around the IDs.
The duplicate add does not increase size. S05 is added and then removed, so the original Robotics membership is restored before the comparisons.
21 | COMPLETE JAVA MEMBERSHIP APPLICATION
Save this as SetsExample.java and run main. The TreeSet copies are for sorted display of these string IDs. The actual membership inputs remain HashSet objects.
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;
public class SetsExample {
public static void main(String[] args) {
Set<String> robotics = new HashSet<>(Arrays.asList("S01", "S02", "S03"));
Set<String> coding = new HashSet<>(Arrays.asList("S03", "S04"));
System.out.println(robotics.contains("S02"));
System.out.println(robotics.add("S02"));
System.out.println(robotics.size());
robotics.add("S05");
System.out.println(robotics.remove("S99"));
robotics.remove("S05");
Set<String> both = new HashSet<>(robotics);
both.retainAll(coding);
Set<String> either = new HashSet<>(robotics);
either.addAll(coding);
Set<String> roboticsOnly = new HashSet<>(robotics);
roboticsOnly.removeAll(coding);
Set<String> codingOnly = new HashSet<>(coding);
codingOnly.removeAll(robotics);
System.out.println(new TreeSet<>(both));
System.out.println(new TreeSet<>(either));
System.out.println(new TreeSet<>(roboticsOnly));
System.out.println(new TreeSet<>(codingOnly));
Set<String> required = new HashSet<>(Arrays.asList("S01", "S03"));
boolean requiredIsSubset = robotics.containsAll(required);
boolean roboticsIsSuperset = robotics.containsAll(required);
boolean properSubset = requiredIsSubset && required.size() < robotics.size();
System.out.println(requiredIsSubset);
System.out.println(roboticsIsSuperset);
System.out.println(properSubset);
System.out.println(robotics.equals(
new HashSet<>(Arrays.asList("S03", "S02", "S01"))));
}
}
Java prints true for the membership check, false for the duplicate add, 3 for size and false for the absent removal. The algebra results then display [S03], [S01, S02, S03, S04], [S01, S02] and [S04]. The four final relation checks are true.
requiredIsSubset and roboticsIsSuperset intentionally use the same containsAll expression because they describe the same inclusion relationship from opposite viewpoints.
22 | CONSTRUCT A SMALL SET ADT WITHOUT HASHING
This teaching implementation uses a Python list internally but exposes membership-style operations. It shows that the ADT contract and the underlying representation are separate. Save it as list_set.py if you want to test the operations yourself.
class ListSet:
def __init__(self, values=()):
self._items = []
for value in values:
self.add(value)
def contains(self, value):
return value in self._items
def add(self, value):
if self.contains(value):
return False
self._items.append(value)
return True
def discard(self, value):
if not self.contains(value):
return False
self._items.remove(value)
return True
def size(self):
return len(self._items)
def snapshot(self):
return tuple(self._items)
def union(self, other):
result = ListSet(self._items)
for value in other._items:
result.add(value)
return result
def intersection(self, other):
return ListSet(value for value in self._items if other.contains(value))
def difference(self, other):
return ListSet(value for value in self._items if not other.contains(value))
def issubset(self, other):
return all(other.contains(value) for value in self._items)
def issuperset(self, other):
return other.issubset(self)
add and discard return whether membership changed in this custom API, unlike Python’s built-in methods. union, intersection and difference return new ListSet objects and leave both inputs unchanged. snapshot provides values for inspection, not a promised ordering feature of the ADT.
The example relies on equality checks and cooperative use of the private-by-convention _items field. It is not a replacement for the built-in set in performance-sensitive code.
23 | APPLY SETS TO A CHECK-IN TASK
registered = {"S01", "S02", "S03", "S04"}
raw_scans = ["S01", "S03", "S01", "S99"]
scanned = set(raw_scans)
present = registered & scanned
absent = registered - scanned
unexpected = scanned - registered
print(sorted(present))
print(sorted(absent))
print(sorted(unexpected))
# ['S01', 'S03']
# ['S02', 'S04']
# ['S99']
The event list retains repeated scans; the scanned set represents distinct IDs. Intersection identifies recognised attendees, while the two differences distinguish absence from unrecognised scans.
Do not discard the event list if you still need scan times, repeated-event counts or arrival order. Different representations can support different parts of the same application.
24 | PERFORMANCE BELONGS TO THE IMPLEMENTATION
Built-in hash-based sets can provide expected constant-time membership, addition and removal under suitable hashing and resizing assumptions. That does not mean every individual operation or every possible workload has guaranteed O(1) time. The next lesson explains hashing mechanics in detail.
Our ListSet membership scans values, so it is O(n) worst case. Its pairwise intersection and difference can cost O(nm) with input sizes n and m, because each of n candidates may search the other m values. A naive union also performs repeated membership work.
A set can be represented with other structures, including suitable trees. The logical uniqueness and membership contract does not itself dictate a hash table, iteration order or universal performance bound.
25 | TEST MEMBERSHIP LAWS AND BOUNDARIES
a = {"S01", "S02", "S03"}
b = {"S03", "S04"}
assert a | b == b | a
assert a & b == b & a
assert a - b == {"S01", "S02"}
assert b - a == {"S04"}
assert a - a == set()
assert set() <= a
assert a <= a and not a < a
before = a.copy()
a.add("S01")
assert a == before
assert a.isdisjoint({"S99"})
Test empty inputs, identical membership, complete separation and partial overlap. Include missing-member removal under the exact API policy, and confirm whether a result should mutate an input or create a new set.
When writing assertions, compare membership rather than an incidental printed order. An expected sorted list is appropriate only if the output contract explicitly calls for sorted presentation.
26 | CONSTRUCT, APPLY AND EXPLAIN
A school needs students who attended either an AI workshop or Robotics, students who attended both, students who attended AI only, and confirmation that a project team contains only registered workshop students. Choose the appropriate operations before writing code.
Explain the reason: intersection keeps only shared IDs, therefore it identifies students who attended both. Difference excludes the second membership, so its operand direction determines who remains. A subset test checks every team ID, rather than merely finding any overlap.
The next lesson connects ADT principles to the mechanics of hash tables, sets and maps. Keep logical membership separate from storage choices as you move on.